CF785E.Anton and Permutation

Anton likes permutations, especially he likes to permute their elements. Note that a permutation of n elements is a sequence of numbers {_a_1, _a_2, ..., a__n}, in which every number from 1 to n appears exactly once.

One day Anton got a new permutation and started to play with it. He does the following operation q times: he takes two elements of the permutation and swaps these elements. After each operation he asks his friend Vanya, how many inversions there are in the new permutation. The number of inversions in a permutation is the number of distinct pairs (i, j) such that 1 ≤ i < j ≤ n and a__i > a__j.

Vanya is tired of answering Anton's silly questions. So he asked you to write a program that would answer these questions instead of him.

Initially Anton's permutation was {1, 2, ..., n}, that is a__i = i for all i such that 1 ≤ i ≤ n.

安东喜欢排列，尤其是对排列中的元素进行置换。注意，一个 $n$ 元排列是指一个由数字 $\{a_1,\,a_2,\,...,\,a_n\}$ 构成的序列，其中每个从 $1$ 到 $n$ 的整数恰好出现一次。

有一天，安东得到了一个新的排列，并开始对其进行操作。他共执行 $q$ 次如下操作：每次选取排列中的两个元素并将它们交换。每次操作后，他都会问朋友万尼亚：当前排列中存在多少个逆序对？一个排列中的逆序对是指满足 $1 \le i < j \le n$ 且 $a_i > a_j$ 的不同下标对 $(i,\,j)$ 的个数。

万尼亚已经厌倦了回答安东这些无聊的问题，于是他请你写一个程序来代替他回答这些问题。

初始时，安东的排列为 $\{1,\,2,\,...,\,n\}$，即对所有满足 $1 \le i \le n$ 的 $i$，均有 $a_i = i$。

The first line of the input contains two integers n and q (1 ≤ n ≤ 200 000, 1 ≤ q ≤ 50 000) — the length of the permutation and the number of operations that Anton does.

Each of the following q lines of the input contains two integers l__i and r__i (1 ≤ l__i, r__i ≤ n) — the indices of elements that Anton swaps during the i-th operation. Note that indices of elements that Anton swaps during the i-th operation can coincide. Elements in the permutation are numbered starting with one.

输入的第一行包含两个整数 $n$ 和 $q$（$1 ≤ n ≤ 200\,000$，$1 ≤ q ≤ 50\,000$）——分别表示排列的长度以及 Anton 执行的操作次数。

接下来的 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 ≤ l_i,\,r_i ≤ n$）——表示 Anton 在第 $i$ 次操作中交换的元素下标。注意：在第 $i$ 次操作中，Anton 交换的两个元素下标可能相同。排列中的元素下标从 1 开始编号。

Output q lines. The i-th line of the output is the number of inversions in the Anton's permutation after the i-th operation.

输出 q 行。第 i 行为执行第 i 次操作后 Anton 排列中的逆序对数量。

Consider the first sample.

After the first Anton's operation the permutation will be {1, 2, 3, 5, 4}. There is only one inversion in it: (4, 5).

After the second Anton's operation the permutation will be {1, 5, 3, 2, 4}. There are four inversions: (2, 3), (2, 4), (2, 5) and (3, 4).

After the third Anton's operation the permutation will be {1, 4, 3, 2, 5}. There are three inversions: (2, 3), (2, 4) and (3, 4).

After the fourth Anton's operation the permutation doesn't change, so there are still three inversions.

考虑第一个样例。

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

在 Anton 执行第四次操作后，排列未发生变化，因此逆序对数量仍为三个。