Problem G
Galactic Sabotage

Pichuu has just finished his catching spree in the safari zone and decided to spend the day organising his messy PC, where his Pokemon are stored. A PC has multiple boxes in a row and each box can store an unlimited amount of Pokemon. For simplicity, you can assume that the Pokemon in a box are also arranged in a row. Thus, we can define an ordering on Pokemon in the PC, where Pokemon $A$ is before $B$ if and only if $A$ is in a box that is to the left of the box $B$ is in, or $A$ and $B$ are in the same box and $A$ is to the left of $B$. Currently all of Pichuu’s Pokemon are in a single PC box.

He wishes to arrange them in a very specific order, namely he wishes the arrange them such that the the current $i^{th}$ Pokemon in the PC becomes the $A_{i}^{th}$ Pokemon in the PC. Following the ordering as mentioned above.

This PC is a new gen PC that the Pokemon Center recently upgraded, with only one available function, AutoSort. Where he can instantly arrange the Pokemon anywhere he wants as long as they remain in the same box. For example, if the Pokemon in 3 boxes are $[5, 2, 6], [1, 3], [7, 4]$, he can use AutoSort to instantly arrange the Pokemon as such $[2, 5, 6], [1, 3], [4, 7]$.
Note that each Pokemon must remain in the same box.

Team Galactic have discovered this and plan on using this opportunity to annoy their enemy. They have hacked the PC and is able to manipulate where Pichuu’s Pokemon are. However, they are limited to only being able to separate the Pokemon into $K \leq N$ contiguous segments and distributing the segments into separate boxes while maintaining the relative ordering.
For example, $[5, 2, 6, 1, 3, 7, 4]$ in box 1, can be separated into $[5, 2, 6]$ in box 1, $[1, 3]$ in box 2 and $[7, 4]$ in box 3.

They wish to do this optimally such that the number of boxes the Pokemon are in is as large as possible. (Making Pichuu have to navigate through different boxes) However, note that they must ensure Pichuu’s can still sort his Pokemon using the AutoSort function. Since if Pichuu is unable to sort his Pokemon, he will be so angry that he goes to Galactic HQ and destroy their HQ.

For example, if Team Galactic splits $[3, 1, 2, 5, 4, 6]$ into 3 boxes as such: $[3, 1, 2], [5, 4], [6]$, Pichuu can still sort his Pokemon using the AutoSort function: $[1, 2, 3], [4, 5], [6]$.
However, if Team Galactic splits $[3, 1, 2, 5, 4, 6]$ into 2 boxes as such: $[3, 1], [2, 5, 4, 6]$, Pichuu is not able to sort his Pokemon and will destroy Team Galactic.

Furthermore, Pichuu is very fickle and can change his opinion on his Pokemon, swapping the preferred ordering of two Pokemon. Namely, he can choose two Pokemon currently at position $i$ and $j$ and swap $A_ i$ and $A_ j$.

Team Galactic wants to know the maximum number of boxes they can separate the Pokemon into such that Pichuu can still sort his Pokemon after each swap. As an aspiring new grunt for Team Galactic, help them figure this out!

Constraints

$1 \leq N, M \leq 5 \times 10^5$
$1 \leq A_ i \leq N$
$A_1, \dots , A_ N$ is a permutation.
$1\leq U_ i, V_ i \leq N$

Input

The first line contains a two space-seaprated integers, $N$, the number of Pokemon and $M$ the number of swaps
The second line contains $N$ space-separated integers, $A_1, A_2, \dots , A_ N$, where $A_ i$ represents the position Pichuu wants the Pokemon to be at.
$M$ lines follows, the $i^{th}$ line contains 2 space-separated integers, $U_ i, V_ i$ which means that Pichuu swaps the position currently at position $U_ i$ and $V_ i$.

Output

Output $M + 1$ lines, each containing a single integer.

The first integer represents the answer prior to any swaps, and for $2 \leq i \leq M + 1$, the $i^{th}$ integer represents the answer after the $(i-1)^{th}$ swap.

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

3
3
5
4
3
2

10 8
1 4 3 2 5 6 7 10 9 8 
8 10
4 2
6 7
6 7
2 4
9 10
4 2
8 9

6
8
10
9
10
8
7
9
8