Mumei 每天都会练习一种图片匹配游戏来提高记忆力。在这个游戏中，有 $n$ 种不同的图片，编号为 $1$ 到 $n$，共有 $2n$ 张卡片，每种图片恰好印在两张卡片上。卡片被洗牌后排成一行放在桌面上，图片面朝下。每一轮，Mumei 会翻开一张卡片，然后再翻开另一张；如果两张卡片上的图片相同，她就将它们从桌面上移除；如果不同，她就将它们翻回去。游戏的目标是移除桌面上的所有卡片。

现在是 2044 年，Mumei 已经获得了非凡的记忆力，以至于她在游戏中不会犯任何错误。现在，她遵循特定的步骤来玩这个游戏：

1. 如果她已经见过两张相同的图片，且它们仍然在桌面上，她会翻开这两张卡片并将它们从桌面上移除。
2. 如果不是这种情况，她首先翻开尚未翻开的最左侧的卡片，并查看上面的图片。 (a) 如果她已经见过另一张相同的图片，她会翻开那张卡片并将两张卡片从桌面上移除。 (b) 如果不是这种情况，她继续翻开尚未翻开的最左侧的卡片。如果两张卡片上的图片相同，她将它们从桌面上移除；如果不同，她将它们翻回去。

可以证明，遵循此过程会导致每一轮选择的卡片对是唯一确定的。

你需要编写一个程序，根据桌面上卡片的初始排列，预测 Mumei 从头到尾完成游戏所需的轮数。然而，一个名叫 Belz 的淘气角色认为这个游戏太无聊了，开始随机交换卡片对。请编写一个程序，确定在每次交换后完成整个游戏所需的轮数。

输入格式

第一行包含两个整数 $n$ 和 $q$：图片数量和交换次数 ($1 \le n, q \le 200\,000$)。

第二行包含 $2n$ 个整数：排成一行的卡片上的图片编号。$1$ 到 $n$ 中的每个整数在这一行中恰好出现两次。

接下来的 $q$ 行描述交换操作。每次交换由两个整数 $\ell$ 和 $r$ 表示，意味着交换行中第 $\ell$ 张和第 $r$ 张卡片 ($1 \le \ell < r \le 2n$)。所有交换的效果是累积的：每次交换都应用于已经执行过所有先前交换的行。

输出格式

第一行输出从初始状态完成游戏所需的轮数。

在接下来的 $q$ 行中，输出每次交换后完成游戏所需的轮数。

样例

输入 1

4 2
1 2 3 1 4 4 2 3
1 2
1 4

输出 1

6
6
5