Операция побитового «или» для набора целых положительных чисел, записанных в двоичной системе счисления, устроена следующим образом. Результатом её применения является число, в двоичной записи которого единица устанавливается в тех разрядах, в которых содержится единица хотя бы у одного числа из набора.

В редких случаях побитовое «или» можно использовать для сложения целых положительных чисел, записанных в двоичной системе счисления. Сумма набора чисел равна их побитовому «или», если для каждого разряда имеется не более одного числа из этого набора, у которого в этом разряде находится единица. Такие наборы чисел назовём красивыми.

Задан набор целых положительных чисел a₁, a₂, ..., a_n. Необходимо построить красивый набор целых положительных чисел b₁, b₂, ..., b_n, чтобы для всех i от 1 до n выполнялось условие b_i ≥ a_i, а сумма b₁ + b₂ + ... + b_n была минимальна.

Требуется написать программу, которая по двоичной записи чисел a₁, a₂, ..., a_n определяет двоичную запись минимального значения суммы искомого красивого набора b₁, b₂, ..., b_n.

Обозначим максимальную длину двоичной записи числа во входных данных как max L.

Вам будут начислены баллы за группу, только если пройдены все тесты этой группы и во всех группах, от которых она зависит. Группа 0 соответствует примерам из условия.

Известно, что если сохранить в каждом слове текста первую и последнюю букву, а остальные переставить произвольным образом, получившийся текст по-прежнему можно достаточно свободно прочитать. В лаборатории информатики исследуют аналогичный феномен для числовых последовательностей.

Будем называть последовательность, состоящую из целых положительных чисел, корректной, если первое число в этой последовательности является минимальным, а последнее — максимальным. Например, последовательности $$$[1, 3, 2, 4]$$$ и $$$[1, 2, 1, 2]$$$ являются корректными, а последовательность $$$[1, 3, 2]$$$ — нет.

Задана последовательность $$$[a_1, a_2, \ldots, a_n]$$$. Будем называть отрезок элементов заданной последовательности $$$[a_l, a_{l+1}, \ldots, a_r]$$$ корректным, если он представляет собой корректную последовательность: $$$a_l$$$ является минимальным числом на этом отрезке, а $$$a_r$$$ — максимальным.

В рамках исследования необходимо разбить заданную последовательность на минимальное количество непересекающихся корректных отрезков. Например, последовательность $$$[2, 3, 1, 1, 5, 1]$$$ можно разбить на три корректных отрезка: $$$[2, 3]$$$ и $$$[1, 1, 5]$$$ и $$$[1]$$$.

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

$$$$$$ \begin{array}{|c|c|c|c|} \hline \text{Подзадача} & \text{Баллы} & \text{Ограничения} & \text{Необх. подзадачи} \\ \hline 1 & 30 & n \le 500 & 0 \\ \hline 2 & 30 & n \le 5\,000 & 0, 1 \\ \hline 3 & 40 & n \le 300\,000 & 0, 1, 2 \\ \hline \end{array}$$$$$$

Вам будут начислены баллы за группу, только если пройдены все тесты этой группы и во всех группах, от которых она зависит. Группа $$$0$$$ соответствует примерам из условия.

Новый процессор UL-2018, разработанный в научной лаборатории, предназначен для быстрой обработки массивов. Ключевой особенностью архитектуры нового процессора является операция расслоения отрезка массива.

Рассмотрим массив $$$[a_1, a_2, \ldots, a_n]$$$. Операция расслоения характеризуется двумя целыми числами $$$l$$$ и $$$r$$$ — номером первого и последнего элемента отрезка массива, к которому она применяется. Обозначим операцию расслоения отрезка массива $$$[a_l, a_{l+1}, \ldots, a_r]$$$ как $$$S(l, r)$$$. После выполнения операции $$$S(l, r)$$$ элементы массива на этом отрезке переупорядочиваются следующим образом. Сначала располагаются элементы отрезка с позиций $$$a_{l+1}, a_{l+3}, \ldots$$$, то есть элементы с позиций $$$i$$$, для которых значение $$$i - l$$$ нечетно, их относительный порядок остаётся неизменным. Затем идут элементы отрезка $$$a_l, a_{l+2}, \ldots$$$, то есть элементы с позиций $$$i$$$, для которых значение $$$i-l$$$ четно, они также сохраняют свой относительный порядок.

Например, рассмотрим массив $$$[2, 4, 1, 5, 3, 6, 7, 8]$$$. После выполнения операции расслоения $$$S(2, 6)$$$ изменится порядок элементов на отрезке массива $$$[4, 1, 5, 3, 6]$$$. Новый порядок элементов на этом отрезке следующий: $$$[1, 3, 4, 5, 6]$$$, а весь массив после выполнения этой операции равен $$$[2, 1, 3, 4, 5, 6, 7, 8]$$$.

Для демонстрации возможностей нового процессора решено было использовать операцию расслоения для реализации алгоритма сортировки массива различных чисел. Задан массив, содержащий $$$n$$$ элементов, $$$1 \le n \le 3000$$$. Элементы массива — различные целые числа от $$$1$$$ до $$$n$$$. Необходимо отсортировать заданный массив по возрастанию, используя не более $$$15\,000$$$ операций расслоения отрезка массива.

Например, приведенный выше массив $$$[2, 4, 1, 5, 3, 6, 7, 8]$$$ можно отсортировать, используя две операции расслоения. Сначала выполним продемонстрированную выше операцию $$$S(2, 6)$$$, после которой массив принимает вид $$$[2, 1, 3, 4, 5, 6, 7, 8]$$$, а затем операцию $$$S(1, 2)$$$, массив примет вид $$$[1, 2, 3, 4, 5, 6, 7, 8]$$$.

Требуется написать программу, которая по заданному массиву определит последовательность не более, чем из $$$15\,000$$$ операций расслоения, после выполнения которых заданный массив окажется отсортирован по возрастанию. Минимизировать количество выполненных операций расслоения не требуется, достаточно использовать не более $$$15\,000$$$ операций.

$$$$$$ \begin{array}{|c|c|c|c|} \hline \text{Подзадача} & \text{Баллы} & \text{Ограничения} & \text{Необх. подзадачи} \\ \hline 1 & 20 & n \le 100; \ \text{Существует ответ c } k = 1 & \\ \hline 2 & 30 & n \le 100 & 0, 1 \\ \hline 3 & 30 & n \le 1\,000 & 0-2 \\ \hline 4 & 20 & n \le 3\,000 & 0-3 \\ \hline \end{array}$$$$$$

Вам будут начислены баллы за группу, только если пройдены все тесты этой группы и во всех группах, от которых она зависит. Группа $$$0$$$ соответствует примерам из условия.

В робомарафоне принимают участие n роботов. Роботы должны преодолеть одинаковую дистанцию, передвигаясь по расположенным рядом друг с другом дорожкам шириной один метр каждая. Известно, что расположенный на i-й дорожке робот преодолевает дистанцию за a_i секунд.

В точке старта каждого робота установлено специальное сигнальное устройство, которое должно сработать в момент старта. Чтобы сделать соревнования менее предсказуемыми, судьи перед стартом могут отключить некоторые сигнальные устройства, остальные устройства останутся активными. Только активные устройства срабатывают в тот момент, когда главный судья начинает робомарафон. В начале робомарафона хотя бы одно сигнальное устройство должно являться активным.

Каждый робот начинает движение в тот момент, когда до него доходит стартовый сигнал от активного устройства. Сигнал распространяется со скоростью 1 метр в секунду. Расстояние между дорожками i и j равно |i - j| метров. Обозначим как x_i расстояние от i-й дорожки до ближайшей дорожки, содержащей активное устройство. Робот на i-й дорожке начнёт движение через x_i секунд после старта, преодолеет дистанцию за a_i секунд, и финиширует через f_i = a_i + x_i секунд после старта робомарафона.

Пусть k_i — количество роботов, которые финишировали строго раньше i-го робота. Место i-го робота по итогам робомарафона равно k_i + 1. Если несколько роботов финишируют одновременно, а перед ними финишировали k роботов, то считается, что все они заняли (k + 1)-е место.

Рассмотрим пример. Пусть n = 3, роботы преодолевают дистанцию за a₁ = 2, a₂ = 3 и a₃ = 5 секунд, а активным являлось только сигнальное устройство у третьего робота. Тогда первый робот начнёт движение через 2 секунды после начала забега, f₁ = 4. Второй робот начнёт движение через 1 секунду, f₂ = 4. Третий робот начнёт движение в момент старта, f₃ = 5. По итогам забега первый и второй робот делят первое место, третий робот занимает третье место. Если же, например, сработают все три сигнальных устройства, роботы финишируют через f₁ = 2, f₂ = 3, f₃ = 5, секунд, соответственно. Первый робот займёт первое место, второй робот займёт второе место, а третий робот — третье место.

Как видно из примера, место, которое займёт робот, зависит от того, какие сигнальные устройства являются активными. Необходимо обрабатывать два типа запросов:

1. для каждого робота определить минимальное место, которое он может занять;
2. для каждого робота определить максимальное место, которое он может занять.

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

Группа тестов для подзадачи 3 включает 30 тестов. Каждый из этих тестов оценивается независимо в 1 балл.

Группа тестов для подзадачи 4 включает 50 тестов. Каждый из этих тестов оценивается независимо в 1 балл.

Значения n для всех тестов в подзадаче 3 приведены в следующей таблице.

Значения n для всех тестов в подзадаче 4 приведены в следующей таблице.