Se le da un arreglo que contiene cada número entre ~1~ y ~n~ exactamente una vez. Su tarea consiste en recoger los números de ~1~ a ~n~ en orden creciente. En cada ronda, se recorre el arreglo de izquierda a derecha y se recogen tantos números como sea posible.

Dadas ~m~ operaciones que intercambian dos números en el arreglo, tu tarea es informar el número de rondas después de cada operación.

Entrada

La primera línea tiene dos enteros ~n~ y ~m~: el tamaño del arreglo y el número de operaciones. La siguiente línea tiene ~n~ enteros ~x_1,x_2,\dots,x_n~: los números del arreglo. Por último, hay ~m~ líneas que describen las operaciones. Cada línea tiene dos enteros ~a~ y ~b~: los números en las posiciones ~a~ y ~b~ se intercambian.

Salida

Imprime ~m~ enteros: el número de rondas después de cada intercambio.

Restricciones

• ~1 \leq n, m \leq 2 \cdot 10^5~
• ~1 \leq a,b \leq n~

Ejemplo de Entrada

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

Ejemplo de Salida

2
3
4