E. Лучшая задача о LIS
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Оказывается, это ровно $$$100$$$-я моя задача, которая появляется в каком-то соревновании по программированию. Значит, она должна быть особенной! А что может быть более особенным, чем очередная задача о LIS...

Вам дана перестановка $$$p_1, p_2, \ldots, p_{2n+1}$$$ целых чисел от $$$1$$$ до $$$2n+1$$$. Вам нужно обработать $$$q$$$ обновлений, где $$$i$$$-е обновление заключается в обмене местами $$$p_{u_i}, p_{v_i}$$$.

После каждого обновления найдите любой циклический сдвиг $$$p$$$ с $$$LIS \le n$$$, или определите, что такого сдвига не существует. (Подробности см. в разделе выходных данных).

Здесь $$$LIS(a)$$$ обозначает длину самой длинной строго возрастающей подпоследовательности $$$a$$$.

Взломы в этой задаче отключены. Не спрашивайте почему.

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

Первая строка содержит два целых числа $$$n, q$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le q \le 10^5$$$).

Вторая строка содержит $$$2n+1$$$ целых чисел $$$p_1, p_2, \ldots, p_{2n+1}$$$ ($$$1 \le p_i \le 2n+1$$$, все $$$p_i$$$ различны)  — элементы $$$p$$$.

В $$$i$$$-й из следующих $$$q$$$ строк содержится по два целых числа $$$u_i, v_i$$$ ($$$1 \le u_i, v_i \le 2n+1$$$, $$$u_i \neq v_i$$$)  — обозначающие, что нужно поменять местами элементы $$$p_{u_i}, p_{v_i}$$$ в $$$i$$$-м обновлении.

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

После каждого обновления выведите любое $$$k$$$ $$$(0 \le k \le 2n)$$$, такое, что длина самой длинной возрастающей подпоследовательности $$$(p_{k+1}, p_{k+2}, \ldots, p_{2n+1}, p_1, \ldots, p_k)$$$ не превышает $$$n$$$, или $$$-1$$$, если таких $$$k$$$ нет.

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

После первого обновления наша перестановка становится равна $$$(5, 2, 3, 4, 1)$$$. Мы можем показать, что все ее циклические сдвиги имеют $$$LIS \ge 3$$$.

После второго обновления наша перестановка становится равна $$$(1, 2, 3, 4, 5)$$$. Мы можем показать, что все ее циклические сдвиги имеют $$$LIS \ge 3$$$.

После третьего обновления наша перестановка становится равна $$$(1, 2, 3, 5, 4)$$$. Ее сдвиг на $$$2$$$ равен $$$(3, 5, 4, 1, 2)$$$, и его $$$LIS = 2$$$.

После четвертого обновления наша перестановка становится равна $$$(1, 2, 3, 4, 5)$$$. Мы можем показать, что все ее циклические сдвиги имеют $$$LIS \ge 3$$$.

После пятого обновления наша перестановка становится равна $$$(4, 2, 3, 1, 5)$$$. Ее сдвиг на $$$4$$$ равен $$$(5, 4, 2, 3, 1)$$$, и его $$$LIS = 2$$$.

После пятого обновления наша перестановка становится равна $$$(4, 5, 3, 1, 2)$$$. Ее сдвиг на $$$0$$$ равен $$$(4, 5, 3, 1, 2)$$$, и его $$$LIS = 2$$$.