У вас есть перестановка — массив \(a = [a_1, a_2, \ldots, a_n]\) из различных целых чисел от \(1\) до \(n\). Длина перестановки \(n\) нечётна.
Рассмотрим следующий алгоритм сортировки перестановки по возрастанию.
Вспомогательная процедура алгоритма, \(f(i)\), принимает на вход индекс \(i\) (\(1 \le i \le n-1\)) и делает следующее. Если \(a_i > a_{i+1}\), значения \(a_i\) и \(a_{i+1}\) меняются местами. В противном случае перестановка остаётся без изменений.
Алгоритм состоит из итераций, пронумерованных последовательными целыми числами, начиная с \(1\). На \(i\)-й итерации алгоритм делает следующее:
- если \(i\) нечётно, вызываются \(f(1), f(3), \ldots, f(n - 2)\);
- если \(i\) чётно, вызываются \(f(2), f(4), \ldots, f(n - 1)\).
Можно доказать, что после конечного числа итераций перестановка станет отсортирована по возрастанию.
Через сколько итераций это впервые произойдёт?
Выходные данные
Для каждого набора входных данных выведите число итераций, после которого заданная перестановка впервые окажется отсортирована по возрастанию.
Если заданная перестановка уже отсортирована, выведите \(0\).
Примечание
В первом наборе входных данных перестановка будет меняться следующим образом:
- после \(1\)-й итерации: \([2, 3, 1]\);
- после \(2\)-й итерации: \([2, 1, 3]\);
- после \(3\)-й итерации: \([1, 2, 3]\).
Во втором наборе входных данных перестановка будет меняться следующим образом:
- после \(1\)-й итерации: \([4, 5, 1, 7, 2, 3, 6]\);
- после \(2\)-й итерации: \([4, 1, 5, 2, 7, 3, 6]\);
- после \(3\)-й итерации: \([1, 4, 2, 5, 3, 7, 6]\);
- после \(4\)-й итерации: \([1, 2, 4, 3, 5, 6, 7]\);
- после \(5\)-й итерации: \([1, 2, 3, 4, 5, 6, 7]\).
В третьем наборе входных данных перестановка уже отсортирована, поэтому ответ равен \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
3 2 1
7
4 5 7 1 3 2 6
5
1 2 3 4 5
|
3
5
0
|