← 返回题目列表

Codeforces · 785/E

E. 安东和排列

中文机器翻译题面 查看原题

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)。

第四次安东运算后,排列没有改变,所以仍然有三个反转。