交换统计

题目描述

Y 同学有一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$。

他只会一种非常原始的排序方式：每次选择两个下标 $x,y$，满足 $1 \le x < y \le n$，然后交换 $a_x$ 与 $a_y$。

现在一共会进行 $q$ 次交换操作。对于每次交换操作完成后的序列，你需要统计满足

$a_i > a_{i+1}$

的下标 $i$ 的个数，其中 $1 \le i < n$。

换句话说，你需要在每次交换后输出当前序列中相邻逆序对的数量。

输入格式

第一行包含两个整数 $n,q$，分别表示序列长度和交换次数。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示初始序列。

接下来 $q$ 行，每行包含两个整数 $x,y$，表示交换位置 $x$ 和位置 $y$ 上的元素。

输出格式

输出共 $q$ 行。

第 $i$ 行输出第 $i$ 次交换完成后，满足 $a_j > a_{j+1}$ 的下标 $j$ 的个数。

样例输入 #1

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

样例输出 #1

2
3
1

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le n,q \le 2\times 10^5$，$1 \le a_i \le n$，$1 \le x < y \le n$。

• 特殊性质 A：所有交换操作均满足 $y=x+1$。
• 特殊性质 B：初始序列单调不降。