E. Сортировка по-хулигански
ограничение по времени на тест
10 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Для перестановки $$$p$$$ длины $$$n$$$ мы определяем хулиганский обмен следующим образом:

  • Пусть $$$i$$$ — индекс наибольшего элемента $$$p_i$$$ такого, что $$$p_i \neq i$$$.
  • Пусть $$$j$$$ — индекс самого маленького элемента $$$p_j$$$, такого, что $$$i < j$$$.
  • Поменяйте местами $$$p_i$$$ и $$$p_j$$$.

Мы определяем $$$f(p)$$$ как количество хулиганских обменов, которые нужно выполнить, пока $$$p$$$ не станет отсортированной. Обратите внимание, что если $$$p$$$ является тождественной перестановкой, то $$$f(p)=0$$$.

Вам даны $$$n$$$ и перестановка $$$p$$$ длины $$$n$$$. Вам нужно обработать следующие $$$q$$$ обновлений.

В каждом обновлении вам даются два целых числа $$$x$$$ и $$$y$$$. Нужно поменять местами $$$p_x$$$ и $$$p_y$$$ и затем найти значение $$$f(p)$$$.

Обратите внимание, что обновления сохраняются. Изменения, внесенные в перестановку $$$p$$$, будут применяться при обработке будущих обновлений.

Входные данные

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$2 \le n \le 5 \cdot 10^5$$$, $$$1 \le q \le 5 \cdot 10^4$$$) — длину перестановки и количество обновлений.

Вторая строка содержит $$$n$$$ целых $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \leq p_i \leq n$$$) — перестановку $$$p$$$. Все элементы $$$p$$$ различны.

В $$$i$$$-й из следующих $$$q$$$ строк ввода содержатся два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i < y_i \le n$$$), описывающие $$$i$$$-е обновление.

Выходные данные

После каждого обновления выведите $$$f(p)$$$.

Пример
Входные данные
8 5
6 2 1 5 3 4 7 8
1 8
2 3
4 7
7 8
3 6
Выходные данные
5
6
9
8
7
Примечание

После первого обновления мы имеем $$$f(p)=5$$$. $$$5$$$ хулиганских обменов изображены ниже:

  • $$$[\mathbf{1}, 2, \mathbf{8}, 5, 3, 4, 7, 6]$$$,
  • $$$[1, 2, \mathbf{3}, 5, \mathbf{8}, 4, 7, 6]$$$,
  • $$$[1, 2, 3, 5, \mathbf{4}, \mathbf{8}, 7, 6]$$$,
  • $$$[1, 2, 3, 5, 4, \mathbf{6}, 7, \mathbf{8}]$$$,
  • $$$[1, 2, 3, \mathbf{4}, \mathbf{5}, 6, 7, 8]$$$.