У Джонни новая игрушка. Как вы можете догадаться, она немного необычная. Игрушка является перестановкой $$$P$$$ чисел от $$$1$$$ до $$$n$$$, записанных в строку друг за другом.

Для каждого $$$i$$$ от $$$1$$$ до $$$n - 1$$$, между $$$P_i$$$ и $$$P_{i + 1}$$$ написан вес $$$W_i$$$, и эти веса также образуют перестановку чисел от $$$1$$$ до $$$n - 1$$$. Дополнительно есть веса $$$W_0 = W_n = 0$$$.

Инструкция гласит, что отрезок $$$[L, R]$$$ является хорошим, если $$$W_{L - 1} < W_i$$$ и $$$W_R < W_i$$$ для всех $$$i$$$ из $$$\{L, L + 1, \ldots, R - 1\}$$$. Для такого отрезка она также определяет $$$W_M$$$ как минимум из множества $$$\{W_L, W_{L + 1}, \ldots, W_{R - 1}\}$$$.

Теперь начинается веселье. За один ход, игрок может выбрать один из хороших подотрезков, разрезать на $$$[L, M]$$$ и $$$[M + 1, R]$$$ и поменять местами эти части. Более точно, до операции выбранный подотрезок игрушки выглядел следующим образом: $$$$$$W_{L - 1}, P_L, W_L, \ldots, W_{M - 1}, P_M, W_M, P_{M + 1}, W_{M + 1}, \ldots, W_{R - 1}, P_R, W_R$$$$$$ А после, он стал выглядеть так: $$$$$$W_{L - 1}, P_{M + 1}, W_{M + 1}, \ldots, W_{R - 1}, P_R, W_M, P_L, W_L, \ldots, W_{M - 1}, P_M, W_R$$$$$$

Такая операция может быть выполнена несколько раз (возможно, ноль), и целью является получить минимальное возможное количество инверсий в $$$P$$$.

Младшая сестра Джонни, Меган, считает, что правила слишком запутанные, поэтому она хочет проверить своего брата, выбирая некоторые пары индексов $$$X$$$ и $$$Y$$$, и меняя местами $$$P_X$$$ и $$$P_Y$$$ ($$$X$$$ может быть равно $$$Y$$$). После каждого действия сестры, Джонни интересуется, какого минимального количества инверсий можно достичь, начиная с текущего $$$P$$$ и делая корректные действия?

Вы можете считать, что входные данные были сгенерированы случайно. $$$P$$$ и $$$W$$$ были выбраны случайно и равновероятно среди всех перестановок, а запросы Меган были выбраны случайно и равновероятно среди всех пар индексов.