Вам надано масив, який містить кожне число між ~1…n~ рівно один раз. Ваше завдання зібрати числа від 1 до ~n~ у порядку зростання.

У кожному раунді ви проходите по масиву зліва направо і збираєте якомога більше чисел. Дано ~m~ операцій, які міняють місцями два числа в масиві.

Ваше завдання — повідомити кількість раундів після кожної операції.

Обмеження

• ~1≤n,m≤2⋅10^5~
• ~1≤a,b≤n~

Формат вхідних даних

У першому рядку є два цілі числа ~n~ і ~m~: розмір масиву та кількість операцій.

У наступному рядку є ~n~ цілих чисел ~x_1 ​ , x_2 ​ ,…, x_n~ ​ : числа в масиві.

Нарешті, є ~m~ рядків, які описують операції. У кожному рядку є два цілих числа ~a~ і ~b~: числа на позиціях ~a~ і ~b~ поміняти місцями.

Формат вихідних даних

Вивести ~m~ цілих чисел: кількість раундів після кожної заміни.

Приклад вхідних даних

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

Приклад вихідних даних

2
3
4