Оказывается, это ровно \(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\).
Взломы в этой задаче отключены. Не спрашивайте почему.
Выходные данные
После каждого обновления выведите любое \(k\) \((0 \le k \le 2n)\), такое, что длина самой длинной возрастающей подпоследовательности \((p_{k+1}, p_{k+2}, \ldots, p_{2n+1}, p_1, \ldots, p_k)\) не превышает \(n\), или \(-1\), если таких \(k\) нет.
Примечание
После первого обновления наша перестановка становится равна \((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\).