- Описание
- Отправленные решения
9. Забавная очередь
У вас есть изначально пустой массив $v$ и $N$ возможных операций, которые можно совершить с этим массивом. Элементы массива нумеруются, начиная с 0. Операция может относиться к одному из типов:
- Вставить элемент $x$ в конец массива $v$;
- Вставить элемент $x$ в начало массива $v$;
- Удалить элемент из конца массива $v$;
- Удалить элемент из начала массива $v$;
- Применить XOR Перестановку с параметром $x$ к массиву $v$.
- Получить максимальный номер, который в данный момент содержится в $v$.
XOR Перестановка с параметром $x$ — это перестановка вида $p_i = i \oplus x$, где $\oplus$ — это операция XOR. Гарантируется, что все перестановки корректны. Также, при выполнении операции удаления необходимо вывести значение элемента, который был удален из массива.
Формат ввода
Первая строка входных данных содержит одно целое число $N$ — количество операций ($1 \leq N \leq 5 \cdot 10^5$). Затем следуют описания операций. Каждая операция начинается с одного целого числа, обозначающего ее тип, затем для операций 1, 2 и 5 следует целое число $x$ ($1 \leq x \leq 5 \cdot 10^5$).
Формат вывода
Для каждой операции типа 3, 4 и 6 выводите ее результат (значение удаленного элемента или запрашиваемый максимум).
Ограничения
Ограничение времени
1 с
Ограничение памяти
256 МБ
Пример 1
12
1 3
2 3
6
1 7
2 1
6
5 1
3
4
6
3
6
3
7
3
3
7
7
1