时空限制

1S/512M

题目描述

apiadu 有一个长度为 $n$ 的序列 $a$，他想对这个序列排序，使得这个序列单调不降。

但 apiadu 只是个编程新手，所以他只会一种非常原始的排序方式：每次选择 $1 \le x < y \le n$，然后交换 $a_x$ 与 $a_y$。

apiadu 想知道他的排序方式是否有效，你需要在每次交换两个数后，输出这个序列中有多少个 $1 \le i < n$ 满足 $a_i > a_{i + 1}$。

格式

输入格式

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

第二行包含 $n$ 个整数 $a_1,a_2 ,\cdots a_n$。表示需要排序的数组

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

输出格式

共 $q$ 行，每行一个整数，表示每次交换后满足 $a_i > a_{i + 1}$ 的下标 $i$ 的数量。

样例

样例输入 #1

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

样例输出 #1

2
3
1

样例解释 #1

初始序列为 $[2, 4, 3, 5, 1]$。

• 第一次交换位置 $1, 2$：序列变为 $[4, 2, 3, 5, 1]$。满足 $a_i > a_{i+1}$ 的位置 $i$ 有 $1(4>2)$ 和 $4(5>1)$，共 $2$ 个。
• 第二次交换位置 $3, 5$：序列变为 $[4, 2, 1, 5, 3]$。满足 $a_i > a_{i+1}$ 的位置 $i$ 有 $1(4>2)$，$2(2>1)$ 和 $4(5>3)$，共 $3$ 个。
• 第三次交换位置 $2, 4$：序列变为 $[4, 5, 1, 2, 3]$。满足 $a_i > a_{i+1}$ 的位置 $i$ 只有 $2(5>1)$，共 $1$ 个。

数据规模

对于 $100\%$ 的数据，$1 \le n, q \le 5000$，$1 \le a_i \le n$，$1 \le x < y \le n$。