CF1685E.The Ultimate LIS Problem

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.

事实证明，这恰好是我出现在某场编程竞赛中的第 $100$ 个题目。因此它必须很特别！而还有什么能比另一个关于最长递增子序列（LIS）的题目更特别呢？

你将得到一个由整数 $1$ 到 $2n+1$ 构成的排列 $p_1, p_2, \ldots, p_{2n+1}$。你需要处理 $q$ 次更新，其中第 $i$ 次更新交换 $p_{u_i}$ 与 $p_{v_i}$。

每次更新后，请找出 $p$ 的任意一个循环移位，使得其最长严格递增子序列（LIS）长度不超过 $n$；若不存在这样的循环移位，则判定其不存在。（具体输出格式详见“输出”部分）

此处 $LIS(a)$ 表示序列 $a$ 的最长严格递增子序列 的长度。

本题禁用 Hack 功能。别问为什么。

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.

输入的第一行包含两个整数 $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$ 的元素。

接下来的 $q$ 行中，第 $i$ 行包含两个整数 $u_i, v_i$（$1 \le u_i, v_i \le 2n+1$，且 $u_i \neq v_i$），表示在第 $i$ 次更新中需交换元素 $p_{u_i}$ 与 $p_{v_i}$。

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

每次更新后，输出任意一个 $k$（$0 \le k \le 2n$），使得序列 $(p_{k+1}, p_{k+2}, \ldots, p_{2n+1}, p_1, \ldots, p_k)$ 的最长递增子序列长度不超过 $n$；若不存在满足条件的 $k$，则输出 $-1$。

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

第一次更新后，我们的排列变为 $(5, 2, 3, 4, 1)$。我们可以证明其所有循环移位的最长递增子序列长度（$LIS$）均满足 $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$。