Для перестановки \(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\), будут применяться при обработке будущих обновлений.