Вы обнаружили, что задачи в контесте были перемешаны, и поэтому хотите проанализировать их сложность.

Вы считаете, что сложность каждой из $$$n$$$ задач задаётся перестановкой $$$p = (p_1, \cdots , p_n)$$$ (перестановка длины $$$n$$$ содержит каждое из чисел от $$$1$$$ до $$$n$$$ в точности 1 раз).

Для каждого числа $$$k$$$ вы хотите понять, верно ли, что $$$k$$$ самых простых задач (под номерами $$$1, \cdots , k$$$) находятся в перестановке строго раньше, чем самые сложные $$$k$$$ задач (под номерами $$$n, \cdots , n-k+1$$$).

Пусть индексы $$$k$$$ самых простых задач задаются множеством $$$A_k$$$, а самых сложных задач – множеством $$$B_k$$$.

Тогда для числа $$$k$$$ необходимо проверить, что для любых $$$a \in A_k, b \in B_k$$$ верно, что $$$a \lt b$$$.

Вам же нужно найти максимально возможное $$$k \ge 1$$$, для которого соответствующие множества $$$A_k, B_k$$$ будут соответствовать условию выше, или сообщить, что такого $$$k$$$ не существует.

Как известно, Земля вращается вокруг Солнца, в то время как сама Солнечная система движется в пространстве и так далее.

$$$Andrew-13$$$ стало интересно, может ли сумма этих перемещений складываться в точности в ноль. Поэтому он предлагает вам решить следующую задачу:

Известно, что движение некоторого объекта описывается векторами $$$\vec{v_1}, \cdots ,\vec{v_n}$$$. Вам необходимо выяснить, может ли сумма этих векторов равняться нулевому вектору.

Однако вместо векторов вам лишь заданы их возможные длины (направления векторов могут быть произвольными). Длины задаются отрезками, то есть вектор номер $$$i$$$ может иметь произвольную длину, лежащую в отрезке $$$[l_i; r_i]$$$.

Для вектора $$$\vec{v} = (x, y, z)$$$ его длиной называется $$$|\vec{v}| = \sqrt{x^2 + y^2 + z^2}$$$.

Верите ли вы в альтернативные миры? Группа исследователей обнаружила аномалию, которая может указывать на существование параллельных реальностей. Чтобы подтвердить теорию или её опровергнуть, им нужно решить следующую задачу:

Дано мультимножество $$$a$$$, состоящее из чисел $$$a_1, \cdots, a_n$$$. Необходимо разделить его на некоторый набор непустых мультимножеств $$$S_1, \cdots, S_k$$$ так, чтобы максимизировать сумму соответствующих им медиан.

Другими словами, нужно выбрать число мультимножеств $$$k$$$ и отправить каждый элемент мультимножества $$$a$$$ в точности в одно из множеств $$$S_1, \cdots, S_k$$$. Затем необходимо посчитать $$$x = med(S_1) + med(S_2) + \cdots + med(S_k)$$$.

В качестве ответа необходимо найти максимально возможное $$$x$$$.

В данной задаче для отсортированного множества $$$S$$$ из элементов $$$s_1, \cdots, s_m$$$ (расположенных в порядке возрастания) медиана определяется следующим образом: $$$med(S) = s_{\lceil \frac{n+1}{2} \rceil}$$$.

Например: $$$med(\{1, 5, 13\}) = 5$$$, $$$med(\{1, 5, 7, 13\}) = 7$$$.

Верите ли вы в альтернативные миры? Группа исследователей обнаружила аномалию, которая может указывать на существование параллельных реальностей. Чтобы подтвердить теорию или её опровергнуть, им нужно решить следующую задачу:

Дано мультимножество $$$a$$$, состоящее из чисел $$$a_1, \cdots, a_n$$$. Необходимо разделить его на некоторый набор непустых мультимножеств $$$S_1, \cdots, S_k$$$ так, чтобы максимизировать сумму соответствующих им медиан.

Другими словами, нужно выбрать число мультимножеств $$$k$$$ и отправить каждый элемент мультимножества $$$a$$$ в точности в одно из множеств $$$S_1, \cdots, S_k$$$. Затем необходимо посчитать $$$x = med(S_1) + med(S_2) + \cdots + med(S_k)$$$.

В качестве ответа необходимо найти максимально возможное $$$x$$$.

В данной задаче для отсортированного множества $$$S$$$ из элементов $$$s_1, \cdots, s_m$$$ (расположенных в порядке возрастания) медиана определяется следующим образом: $$$med(S) = (s_{\lceil \frac{n}{2} \rceil} + s_{\lceil \frac{n+1}{2} \rceil}) / 2$$$.

Например: $$$med(\{1, 5, 13\}) = 5$$$, $$$med(\{1, 5, 7, 13\}) = 6$$$.

Проделав долгий путь в поисках древних сокровищ, Оливер готов приступить к финальному испытанию.

Оливер находится в системе подземных комнат, соединённых туннелями. Чтобы избежать ловушек, каждый туннель можно пройти только в одном направлении.

Изначально Оливер находится в комнате $$$1$$$, а сокровище – в комнате $$$n$$$. Однако везде абсолютная темнота, поэтому, чтобы добраться до комнаты $$$n$$$, он будет использовать имеющиеся у него $$$k$$$ переносных ламп. Когда Оливер находится в комнате, он может либо поставить в неё лампу, если у него на руках остаётся хотя бы 1 лампа (если в комнате темно), либо забрать лампу оттуда (если он туда её до этого ставил). Однако перемещаться по туннелю $$$u → v$$$, исходящему из его комнаты $$$u$$$, он может только в том случае, если хотя бы в одной из комнат $$$u, v$$$ находится лампа, которая освещает проход (освещённая комната освещает все проходы, входящие и исходящие из этой комнаты).

Каждая лампа сама по себе является ценным артефактом Оливера, поэтому он хочет пройти путь до комнаты $$$n$$$ и сохранить все лампы при себе, а не разбросанными по лабиринту.

В то же время Оливер может использовать силу ламп, чтобы освещать большие пространства. Изначально у него есть массив $$$c$$$ особых комнат, в котором содержится только комната $$$1$$$ (то есть $$$c = [1]$$$). Если Оливер ставит хоть одну из своих ламп в комнату $$$x$$$, которая находится в массиве $$$c$$$, то все комнаты из массива $$$c$$$ становятся освещёнными.

При этом каждый тринадцатый раз, когда Оливер заходит в одну и ту же комнату $$$u$$$, если из неё есть ребро в комнату, находящуюся в массиве $$$c$$$, то данная комната $$$u$$$ добавляется в массив $$$c$$$.

Помогите Оливеру определить, может ли он добраться до сокровища при заданных условиях.

Сортировка Таноса является одной из сортировок, которая работает за линейное от длины массива время.

Алгоритм сортировки следующий:

1) Если массив $$$a = (a_1, \cdots , a_n)$$$ уже отсортирован, то процесс завершается. Массив считается отсортированным, если для каждого $$$i$$$ от $$$2$$$ до $$$n$$$ верно, что $$$a_{i-1} \le a_i$$$.

2) Иначе случайным образом выбираются либо первые $$$\lceil \frac{n}{2} \rceil$$$ элементов массива, либо последние $$$\lfloor \frac{n}{2} \rfloor$$$ элементов. Все они удаляются, и алгоритм переходит к шагу 1.

Например, сортировка массива $$$[10, 4, 5, 6, 8]$$$ может выглядеть следующим образом:

$$$[10, 4, 5, 6, 8]$$$ -> $$$[6, 8]$$$

Или:

$$$[10, 4, 5, 6, 8]$$$ -> $$$[10, 4, 5]$$$ -> $$$[10, 4]$$$ -> $$$[10]$$$

Поскольку при сортировке Таноса много элементов может исчезнуть, для массива $$$a$$$ определим $$$f(a)$$$ как математическое ожидание числа элементов, оставшихся в итоговом массиве.

Вам дан некоторый массив $$$a$$$.

Необходимо обработать следующие запросы:

$$$i, x$$$ – присвоить $$$a_i := x$$$.

После каждого запроса необходимо вывести $$$f(a)$$$ для текущего массива.

После долгих исследований древнего шифра вы уверены, что близки как никогда к его расшифровке.

Однако для этого вам нужно восстановить массив $$$a$$$ длины $$$n$$$, который обладает некоторыми свойствами, или выяснить, что такого массива не существует.

1) Все элементы массива $$$a$$$ – целые, неотрицательные числа, не превышающие $$$10^{18}$$$. При этом все элементы массива $$$a$$$ различны.

2) Для каждого индекса $$$i$$$ от $$$1$$$ до $$$n$$$ вам известен индекс $$$j \ne i$$$ такой, что для любого $$$k$$$ $$$(k \ne i, k \ne j)$$$ выполняется $$$|a_k - a_i| \gt |a_i - a_j|$$$.

3) Среди всех массивов, соответствующих условиям $$$1$$$ и $$$2$$$, у массива $$$a$$$ максимальный элемент минимально возможный.

Если существует несколько массивов, соответствующих условиям $$$1, 2$$$ и $$$3$$$, то вы можете вывести любой из них.