Вам дана перестановка \(p\) размера \(n\) (перестановка размера \(n\) — это массив размера \(n\), в котором каждое целое число от \(1\) до \(n\) встречается ровно один раз).
Вы можете выполнить следующую операцию любое количество раз (возможно, ноль):
- выбрать два различных элемента \(x\) и \(y\) и удалить их из перестановки;
- вставить минимум из \(x\) и \(y\) в перестановку таким образом, чтобы он стал первым элементом;
- вставить максимум из \(x\) и \(y\) в перестановку таким образом, чтобы он стал последним элементом;
Например, если \(p = [1, 5, 4, 2, 3]\), и мы хотим применить операцию к элементам \(3\) и \(5\), тогда после первого шага операции \(p = [1, 4, 2]\); а после вставки элементов \(p = [3, 1, 4, 2, 5]\).
Ваша задача — определить минимальное количество вышеописанных операций, позволяющих отсортировать перестановку \(p\) в возрастающем порядке (т. е. преобразуйте \(p\) таким образом, что \(p_1 < p_2 < \dots < p_n\)).