I. Obada-utiful Graph
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Obada is Osama's brother, and a former teammate of Tareq too. Do you know what that means? You guessed it, the Blender of Standards again. Obada is a bit smarter than Osama. He can make problems using the Blender that does not actually look like a Blender problem.

Obada will give you an Obada-utiful Graph. It's a graph that is given in a weird way.

It's an undirected graph with $$$N$$$ vertices given as a permutation $$$P$$$ such that there is an undirected edge between vertices $$$u$$$ and $$$v$$$ if:

  • $$$u \lt v$$$ and $$$P_u \lt P_v$$$.
Obada asks you $$$Q$$$ queries. Each query contains two integers $$$(i, j)$$$ that you have to:
  1. swap $$$(P_i,P_j)$$$.
  2. update the graph structure with correspondence to the update in permutation $$$P$$$ (it might add/remove some edges).
  3. find the number of connected components in the graph.
Input

The first line of the input contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \le N \le 10^5$$$), ($$$1 \le Q \le 10^5$$$) — the number of vertices in the graph and the number of queries.

The second line contains $$$N$$$ distinct integers $$$P_1, P_2, \dots, P_N$$$ $$$(1 \le P_i \le N)$$$ — the permutation $$$P$$$.

Each of the next $$$Q$$$ lines contain two integers $$$i$$$ and $$$j$$$ $$$(1 \le i \lt j \le N)$$$ — the description of the queries.

Output

For each query print a single line — the number of connected components in the graph after the first $$$i$$$ queries.

Example
Input
3 2
1 2 3
1 3
2 3
Output
3
2
Note

Sample explanation:

  1. Initially the graph contains one connected component (there are edges between $$$(1, 2)$$$, $$$(1, 3)$$$ and $$$(2, 3)$$$).
  2. After the first query, the graph contains no edges, and thus it contains three connected components.
  3. After the second query, the graph contains one edge between $$$1$$$ and $$$2$$$, and thus it contains two connected components $$$\{1, 2\}$$$ and $$$\{3\}$$$.