Вам надано масив, який містить кожне число між \(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