The Ultimate LIS Problem

给定一个长为 $2n+1$ 的排列，然后进行 $m$ 次操作，每次操作是交换 $p_{u_i}$ 与 $p_{v_i}$。 在每次操作后，找到一个 $k$，使得排列向左循环移位 $k$ 次后得到的排列的 LIS 小于等于 $n$，或判断不存在这样的 $k$。 向左循环移位 $k$ 次后的排列是 $\{p_{k+1},...,p_n,p_1,...,p_k\}$。 第一行 $n,m$。$(n,m\le10^5)$ 第二行 $2n+1$ 个数表示这个排列。 接下来 $m$ 行每行一个操作。

It turns out that this is exactly the $ 100 $ -th problem of mine that appears in some programming competition. So it has to be special! And what can be more special than another problem about LIS... You are given a permutation $ p_1, p_2, \ldots, p_{2n+1} $ of integers from $ 1 $ to $ 2n+1 $ . You will have to process $ q $ updates, where the $ i $ -th update consists in swapping $ p_{u_i}, p_{v_i} $ . After each update, find any cyclic shift of $ p $ with $ LIS \le n $ , or determine that there is no such shift. (Refer to the output section for details). Here $ LIS(a) $ denotes the length of [longest strictly increasing subsequence](https://en.wikipedia.org/wiki/Longest_increasing_subsequence) of $ a $ . Hacks are disabled in this problem. Don't ask why.

The first line of the input contains two integers $ n, q $ ( $ 2 \le n \le 10^5 $ , $ 1 \le q \le 10^5 $ ). The second line of the input contains $ 2n+1 $ integers $ p_1, p_2, \ldots, p_{2n+1} $ ( $ 1 \le p_i \le 2n+1 $ , all $ p_i $ are distinct) — the elements of $ p $ . The $ i $ -th of the next $ q $ lines contains two integers $ u_i, v_i $ ( $ 1 \le u_i, v_i \le 2n+1 $ , $ u_i \neq v_i $ ) — indicating that you have to swap elements $ p_{u_i}, p_{v_i} $ in the $ i $ -th update.

After each update, output any $ k $ $ (0 \le k \le 2n) $ , such that the length of the longest increasing subsequence of $ (p_{k+1}, p_{k+2}, \ldots, p_{2n+1}, p_1, \ldots, p_k) $ doesn't exceed $ n $ , or $ -1 $ , if there is no such $ 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

After the first update, our permutation becomes $ (5, 2, 3, 4, 1) $ . We can show that all its cyclic shifts have $ LIS \ge 3 $ . After the second update, our permutation becomes $ (1, 2, 3, 4, 5) $ . We can show that all its cyclic shifts have $ LIS \ge 3 $ . After the third update, our permutation becomes $ (1, 2, 3, 5, 4) $ . Its shift by $ 2 $ is $ (3, 5, 4, 1, 2) $ , and its $ LIS = 2 $ . After the fourth update, our permutation becomes $ (1, 2, 3, 4, 5) $ . We can show that all its cyclic shifts have $ LIS \ge 3 $ . After the fifth update, our permutation becomes $ (4, 2, 3, 1, 5) $ . Its shift by $ 4 $ is $ (5, 4, 2, 3, 1) $ , and its $ LIS = 2 $ . After the fifth update, our permutation becomes $ (4, 5, 3, 1, 2) $ . Its shift by $ 0 $ is $ (4, 5, 3, 1, 2) $ , and its $ LIS = 2 $ .