如果一个整数数组 $a_1, a_2, \dots, a_m$ 的逆序对数量为奇数，则称其为“奇”数组，否则称为“偶”数组。 回想一下，逆序对是指满足 $1 \le i < j \le m$ 且 $a_i > a_j$ 的数对 $(i, j)$。例如，在数组 $[2, 4, 1, 3]$ 中有 3 个逆序对：$(1, 3), (2, 3), (2, 4)$（因为 $a_1 > a_3, a_2 > a_3, a_2 > a_4$），因此它是奇数组。

给定一个 $1$ 到 $n$ 的排列 $p_1, p_2, \dots, p_n$，我们将其最长奇子序列的长度称为该排列的“美感度”。如果不存在奇子序列，则美感度为 $-1$。例如，排列 $(1, 2, 3)$ 的美感度为 $-1$，因为它的每个子序列都是偶数组；$(4, 1, 2, 3)$ 的美感度为 $4$，因为整个排列是奇数组；$(4, 1, 3, 2)$ 的美感度为 $3$，因为整个排列是偶数组，但子序列 $(4, 3, 2)$ 是奇数组。

给定一个初始排列 $p_1, p_2, \dots, p_n$。共有 $q$ 次更新请求。在第 $i$ 次请求后，我们需要交换 $p_{u_i}$ 和 $p_{v_i}$。 请在每次请求后求出该排列的美感度。

回想一下，如果数组 $b$ 可以通过从 $c$ 中删除某些（可能为零或全部）元素得到，则称 $b$ 是 $c$ 的子序列。 回想一下，一个 $1$ 到 $n$ 的排列是一个长度为 $n$ 且包含 $1$ 到 $n$ 每个数字恰好一次的数组。

输入格式

第一行包含两个整数 $n, q$ ($1 \le n, q \le 2 \cdot 10^5$)，分别表示排列长度和查询次数。 第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$，所有 $p_i$ 互不相同)，表示初始排列 $p$。 接下来的 $q$ 行，每行包含两个整数 $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，表示在第 $i$ 次查询后，你需要交换 $p_{u_i}$ 和 $p_{v_i}$。

输出格式

输出 $q$ 个整数，表示每次更新请求后的排列美感度。

样例

输入 1

5 6
2 1 3 4 5
1 2
1 2
1 4
2 1
3 5
1 3

输出 1

-1
5
4
5
3
5

说明

• 第一次查询后，排列为 $(1, 2, 3, 4, 5)$。其中不存在奇子序列。
• 第二次查询后，排列为 $(2, 1, 3, 4, 5)$。整个排列是奇数组，因为它恰好有一个逆序对。
• 第三次查询后，排列为 $(4, 1, 3, 2, 5)$。整个排列是偶数组，但其子序列 $(4, 3, 2, 5)$ 是奇数组。
• 第四次查询后，排列为 $(1, 4, 3, 2, 5)$。整个排列是奇数组。
• 第五次查询后，排列为 $(1, 4, 5, 2, 3)$。整个排列是偶数组，且其所有长度为 $4$ 的子序列均为偶数组，但子序列 $(1, 5, 2)$ 是奇数组。
• 第六次查询后，排列为 $(5, 4, 1, 2, 3)$。整个排列是奇数组。