Anton 喜欢排列,尤其是元素的排列。请注意,n 个元素的排列是一个数字序列 {a1, a2, ..., an},其中从 1 到 n 的每个数字恰好出现一次。
有一天,安东得到了一个新的排列并开始玩它。他执行以下操作 q 次:他取出排列中的两个元素并交换这些元素。每次操作后,他都会问他的朋友 Vanya,新的排列中有多少个倒置。排列中的反转数是满足 1 ≤ i < j ≤ n 且 ai > aj 的不同对 (i, j) 的数量。
万尼亚厌倦了回答安东的愚蠢问题。所以他让你代替他编写一个程序来回答这些问题。
最初 Anton 的排列是 {1, 2, ..., n},即对于所有 i,ai = i,使得 1 ≤ i ≤ n。
输入
输入的第一行包含两个整数 n 和 q (1 ≤ n ≤ 200 000, 1 ≤ q ≤ 50 000) - 排列的长度和 Anton 执行的操作数。
输入的以下 q 行中的每一行都包含两个整数 li 和 ri (1 ≤ li, ri ≤ n) - Anton 在第 i 次操作期间交换的元素的索引。请注意,Anton 在第 i 个操作期间交换的元素索引可以重合。排列中的元素从 1 开始编号。
输出
输出 q 行。输出的第 i 行是第 i 次操作后安东排列的反转次数。
示例
输入 #1
5 4 4 5 2 4 2 5 2 2
输出 #1
1 4 3 3
输入 #2
2 1 2 1
输出 #2
1
输入 #3
6 7 1 4 3 5 2 3 3 3 3 6 2 1 5 1
输出 #3
5 6 7 7 10 11 8
注意
考虑第一个样本。
在第一个 Anton 操作之后,排列将是 {1, 2, 3, 5, 4}。其中只有一个反转:(4, 5)。
第二次 Anton 操作后,排列将为 {1, 5, 3, 2, 4}。有四种反转:(2, 3)、(2, 4)、(2, 5) 和(3, 4)。
第三次 Anton 运算后,排列将为 {1, 4, 3, 2, 5}。存在三种反转:(2, 3)、(2, 4) 和(3, 4)。
第四次安东运算后,排列没有改变,所以仍然有三个反转。