Задача . F. Джонни и новая игрушка

У Джонни новая игрушка. Как вы можете догадаться, она немного необычная. Игрушка является перестановкой \(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\) были выбраны случайно и равновероятно среди всех перестановок, а запросы Меган были выбраны случайно и равновероятно среди всех пар индексов.