当前没有测试数据。

Description

You are given an array that contains each number between 1…n exactly once. Your task is to collect the numbers from 1 to n in increasing order.

On each round, you go through the array from left to right and collect as many numbers as possible.

Given m operations that swap two numbers in the array, your task is to report the number of rounds after each operation.

Input Format

The first line has two integers n and m: the array size and the number of operations.

The next line has n integers x1,x2,…,xn: the numbers in the array.

Finally, there are m lines that describe the operations. Each line has two integers a and b: the numbers at positions a and b are swapped.

Output Format

Print m integers: the number of rounds after each swap.

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

2
3
4

Hint

<li> 1≤n,m≤2⋅10⁵ </li> <li> 1≤a,b≤n </li>

Source

CSES