C. Cutting Cards
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

There are $$$n$$$ cards, numbered from $$$1$$$ to $$$n$$$. A cutting card operation is performed as follows:

  1. Arrange the cards in ascending order according to their index.
  2. Choose a positive integer $$$k\ (1\le k\le n)$$$ and divide the cards into $$$k$$$ piles. Each pile must contain at least one card, and the cards in each pile must have consecutive indexes and be arranged in ascending order from top to bottom.
  3. Rearrange the piles in any order and line them up in a row.
  4. Traverse the piles from left to right, and for each pile, if there are still cards in the pile, take the top card and place it at the end of the arranged cards.
  5. Stop the operation when all the cards have been placed in the arranged sequence.

For example, for five cards $$$\{1,2,3,4,5\}$$$, they can be divided into $$$\{1\},\{2,3\},\{4,5\}$$$, $$$\{1\},\{2\},\{3\},\{4\},\{5\}$$$, or $$$\{1,2,3,4,5\}$$$, but they cannot be divided into $$$\{1\},\{2,5\},\{3,4\}$$$ because this violates the consecutive numbering principle, nor can they be divided into $$$\{1\},\{3,2\},\{4,5\}$$$ because this violates the principle of arranging in ascending order.

For another example, for the already arranged three piles of cards from left to right $$$\{1\},\{4,5\},\{2,3\}$$$, the only possible arranged sequence is $$$\{1,4,2,5,3\}$$$, and it is not possible to obtain $$$\{1,2,4,5,3\}$$$ because this violates the left-to-right traversal order, nor is it possible to obtain $$$\{1,5,2,4,3\}$$$ because this violates the taking-from-top principle.

There is a target arrangement of the cards, and you need to calculate how many different cutting card operations can obtain this target arrangement. Two cutting card operations are different if and only if the way the cards are divided into piles is different or the arrangement of the piles is different.

The target arrangement may be modified, and for each modification, the elements in the two positions of the target arrangement are exchanged, and the answer needs to be output. The modifications are persistent, meaning that previous modifications will be retained.

Input

The first line contains two integers $$$n,Q$$$ ($$$2\le n\le 10^5,1\le Q\le 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le n$$$), representing the initial target arrangement.

The next $$$Q$$$ lines each contain two integers $$$x,y$$$ ($$$1\le x,y\le n,x\neq y$$$), representing the positions to be swapped in each modification.

Output

Output $$$Q+1$$$ lines. The first line outputs the answer before any modifications, and the second to the $$$Q+1$$$-th lines outputs the answer after the first to the $$$Q$$$-th modifications.

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

In the example, there are $$$4$$$ cards, and the initial target sequence is $$$\{1,3,2,4\}$$$. There are three cutting card operations that can obtain the target sequence:

  • $$$\{1,2\},\{3,4\}$$$
  • $$$\{1\},\{3,4\},\{2\}$$$
  • $$$\{1\},\{3\},\{2\},\{4\}$$$

After the first swap, the target sequence becomes $$$\{1,2,3,4\}$$$. There are four cutting card operations that can obtain the target sequence:

  • $$$\{1,2,3,4\}$$$
  • $$$\{1\},\{2,3,4\}$$$
  • $$$\{1\},\{2\},\{3,4\}$$$
  • $$$\{1\},\{2\},\{3\},\{4\}$$$