F. Приличное разделение
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бинарной строкой называется строка, каждый символ которой это $$$\texttt{0}$$$ или $$$\texttt{1}$$$. Назовем бинарную строку приличной, если в ней поровну символов $$$\texttt{0}$$$ и $$$\texttt{1}$$$.

Изначально у вас есть бесконечная бинарная строка $$$t$$$, все символы которой равны $$$\texttt{0}$$$. Вам дана последовательность целых чисел $$$a$$$ из $$$n$$$ обновлений, где $$$a_i$$$ означает, что символ на позиции $$$a_i$$$ будет изменен на противоположный ($$$\texttt{0} \leftrightarrow \texttt{1}$$$). Вам нужно поддерживать и изменять после каждого обновления множество $$$S$$$ непересекающихся отрезков таких, что

  • для каждого отрезка $$$[l,r]$$$ строка $$$t_l \dots t_r$$$ является приличной бинарной строкой, и
  • для каждого индекса $$$i$$$ такого, что $$$t_i = \texttt{1}$$$, существует отрезок $$$[l,r]$$$ в $$$S$$$ такой, что $$$l \leq i \leq r$$$.

Вам нужно выводить только отрезки, которые вы удаляете или добавляете в множество $$$S$$$ после каждого обновления. В вашем ответе добавлений и удалений в $$$S$$$ должно быть не более чем $$$\mathbf{10^6}$$$.

Формально, пусть $$$S_i$$$ — множество отрезков после $$$i$$$-го обновления, где $$$S_0 = \varnothing$$$ (пустое множество). Определим $$$X_i$$$ как множество отрезков, удаленных из множества после $$$i$$$-го обновления, и $$$Y_i$$$ как множество отрезков, добавленных в множество после $$$i$$$-го обновления. Тогда для каждого $$$1 \leq i \leq n$$$ выполняется $$$S_i = (S_{i - 1} \setminus X_i) \cup Y_i$$$. Для каждого $$$1 \leq i \leq n$$$ должно выполняться следующее:

  • $$$\forall a,b \in S_i, (a \neq b) \rightarrow (a \cap b = \varnothing)$$$;
  • $$$X_i \subseteq S_{i - 1}$$$;
  • $$$(S_{i-1} \setminus X_i) \cap Y_i = \varnothing$$$;
  • $$$\displaystyle\sum_{i = 1}^n {(|X_i| + |Y_i|)} \leq 10^6$$$.
Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — количество обновлений.

Каждая из следующих $$$n$$$ строк содержит одно целое число $$$a_i$$$ ($$$1 \leq a_i \leq 2 \cdot 10^5$$$) — номер символа, к которому применяется $$$i$$$-е обновление.

Выходные данные

После $$$i$$$-го обновления сначала одно целое число $$$x_i$$$ — количество отрезков, которое нужно удалить из $$$S$$$ после обновления $$$i$$$.

В каждой из следующих $$$x_i$$$ строк выведите два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l < r \leq 10^6$$$), определяющие отрезок $$$[l,r]$$$, который должен быть удален из $$$S$$$. Каждый из этих отрезков должен быть уникальным и содержаться в $$$S$$$.обозначающее

В следующей строке выведите одно целое число $$$y_i$$$ — количество отрезков, которое нужно добавить в $$$S$$$ после обновления $$$i$$$.

В каждой из следующих $$$y_i$$$ строк выведите два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l < r \leq 10^6$$$), определяющие отрезок $$$[l,r]$$$, который должен быть добавлен в $$$S$$$. Каждый из этих отрезков должен быть уникальным и не содержаться в $$$S$$$.

Общее количество добавлений и удалений после всех обновлений не должно превосходить $$$\mathbf{10^6}$$$.

После каждого обновления после всех удалений и добавлений все отрезки в $$$S$$$ должны быть непересекающимися и покрывать все единицы.

Можно показать, что ответ всегда существует при данных ограничениях.

Пример
Входные данные
5
1
6
5
5
6
Выходные данные
0
1
1 2

0
1
5 6

1
5 6
2
6 7
4 5

1
4 5
0

1
6 7
0
Примечание

В примере вывода приведены дополнительные переводы строк для ясности, вам не обязательно их выводить.

После первого обновления множество индексов, в которых $$$a_i = 1$$$, это $$$\{1\}$$$. Отрезок $$$[1, 2]$$$ добавлен, поэтому $$$S_1 = \{[1, 2]\}$$$, в нем один $$$\texttt{0}$$$ и одна $$$\texttt{1}$$$.

После второго обновления множество индексов, в которых $$$a_i = 1$$$, это $$$\{1, 6\}$$$. Отрезок $$$[5, 6]$$$ добавлен, поэтому $$$S_2 = \{[1, 2], [5, 6]\}$$$, в каждом из них один $$$\texttt{0}$$$ и одна $$$\texttt{1}$$$.

После третьего обновления множество индексов, в которых $$$a_i = 1$$$, это $$$\{1, 5, 6\}$$$. Отрезок $$$[5, 6]$$$ удален, а отрезки $$$[4, 5]$$$ и $$$[6, 7]$$$ добавлены, поэтому $$$S_3 = \{[1, 2], [4, 5], [6, 7]\}$$$, в каждом из них один $$$\texttt{0}$$$ и одна $$$\texttt{1}$$$.

После четвертого обновления множество индексов, в которых $$$a_i = 1$$$, это $$$\{1, 6\}$$$. Отрезок $$$[4, 5]$$$ удален, поэтому $$$S_4 = \{[1, 2], [6, 7]\}$$$, в каждом из которых один $$$\texttt{0}$$$ и одна $$$\texttt{1}$$$.

После пятого обновления множество индексов, в которых $$$a_i = 1$$$, это $$$\{1\}$$$. Отрезок $$$[6, 7]$$$ удален, поэтому $$$S_5 = \{[1, 2]\}$$$, в этом отрезке один $$$\texttt{0}$$$ и одна $$$\texttt{1}$$$.