The Ultimate LIS Problem
Contest: Codeforces Round 794 (Div. 1)
Difficulty rating: 3500
Tags: data structures, greedy

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 of $$$a$$$.

Hacks are disabled in this problem. Don't ask why.

Input format:
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.

Output format:
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$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
2 6
1 2 3 4 5
1 5
1 5
4 5
5 4
1 4
2 5

Example output:
-1
-1
2
-1
4
0

Editorial:
Consider element $$$n+1$$$. Replace for a while $$$n+1$$$ by $$$0$$$, each element $$$\le n$$$ by $$$-1$$$, and each element $$$\ge n+2$$$ by $$$1$$$. It's well-known that for an array of $$$n$$$ of $$$1$$$ and $$$n$$$ of $$$-1$$$ there exists a cyclic shift such that all its prefix sums are nonnegative (which is equivalent to the sequence of these $$$1$$$s and $$$-1$$$s being balanced). Consider such cyclic shift for our array.
It's easy to see now that in this cycle there is no increasing subsequence of length at $$$n+1$$$ of element distinct from $$$n+1$$$. Indeed, in such a subsequence we would have $$$t$$$ of $$$-1$$$s, and then $$$n + 1 - t$$$ of $$$1$$$s, which would mean that $$$t$$$-th $$$1$$$ goes after the $$$t$$$-th $$$-1$$$, meaning that the subsequence isn't balanced.
So, if there is an increasing subsequence of length $$$n+1$$$ in this shift, $$$n+1$$$ is in it.
Let's say there are $$$t$$$ elements $$$\le n$$$ before $$$n+1$$$ in this subsequence and $$$n - t$$$ elements $$$\ge n$$$ after $$$n+1$$$ in this subsequence. As $$$t$$$-th $$$1$$$ goes before $$$t$$$-th $$$-1$$$ in this shift, we get that there are exactly $$$t$$$ elements $$$\ge n+2$$$ in this shift before $$$n+1$$$, and (similarly) exactly $$$n-t$$$ elements $$$\le n$$$ in this shift after $$$n+1$$$. In addition, these two parts form (as ones and minus ones) two separate balanced sequences.
Now, consider a shift in which $$$n+1$$$ is the first element. It's easy to see that if the condition above holds, then in this shift ones and minus ones also form a balanced subsequence. If $$$LIS$$$ of this shift is $$$n+1$$$, it must be the case that $$$n+1$$$ and $$$n$$$ ones form it, which implies that elements $$$n+1, n+2, \ldots, 2n+1$$$ go clockwise in this permutation.
Similarly, after considering a shift in which $$$n+1$$$ is the last element, we get that elements $$$1, 2, \ldots, n+1$$$ go clockwise in this permutation.
It turns out that if all the conditions above hold, then all shifts have $$$LIS \ge n+1$$$. Indeed, consider any shift, elements to the left of $$$n+1$$$ smaller than $$$n+1$$$, $$$n+1$$$, and elements to the right of $$$n+1$$$ larger than $$$n+1$$$ form an increasing subsequence. From the fact that $$$1$$$s and $$$-1$$$s are balanced we get that numbers smaller than $$$n+1$$$ take at least half of the space before $$$n+1$$$, and larger than $$$n+1$$$ take at least half of the space after $$$n+1$$$, so its length is at least $$$n+1$$$.
With all this knowledge, how do we solve the problem?
We will keep track of all the $$$1$$$s and $$$-1$$$s with a segment tree, with queries "smallest prefix sum on the subsegment". When we need to provide the answer after the update, we will do the following:
• Check if the circular segment from $$$n+1$$$ to $$$n+1$$$ is balanced. If not, find the shift that makes $$$1$$$s and $$$-1$$$s balanced, its $$$LIS$$$ is at most $$$n$$$.
• Then, check if $$$n+1, n+2, \ldots, 2n+1$$$ go clockwise in the permutation. If not, then the shift in which $$$n+1$$$ is the first element has $$$LIS\le n$$$.
• Then, check if $$$1, 2, \ldots, n+1$$$ go clockwise in the permutation. If not, then the shift in which $$$n+1$$$ is the last element has $$$LIS\le n$$$.
• Otherwise, output $$$-1$$$.
We check if $$$1, 2, \ldots, n+1$$$ go clockwise by saving the following sum: $$$$$$\sum_{i = 1}^{n} (pos(i\bmod (n+1) + 1) - pos(i))\bmod (2n+1)$$$$$$
If it's $$$2n+1$$$, they go clockwise, else not. We can update this sum in $$$O(1)$$$ per query.
Total complexity is $$$O(\log(n))$$$ per query.