Для перестановки \(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\), будут применяться при обработке будущих обновлений.
Выходные данные
После каждого обновления выведите \(f(p)\).
Примечание
После первого обновления мы имеем \(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]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|