Для массива \([b_1, b_2, \ldots, b_m]\) определим его число инверсий как количество пар \((i, j)\) целых чисел таких, что \(1 \le i < j \le m\) и \(b_i>b_j\). Назовем массив \(b\) нечетным, если его число инверсий нечетно.
Например, массив \([4, 2, 7]\) является нечетным, так как его число инверсий равно \(1\), а массив \([2, 1, 4, 3]\) — нет, так как его число инверсий равно \(2\).
Вам дана перестановка \([p_1, p_2, \ldots, p_n]\) целых чисел от \(1\) до \(n\) (каждое из них встречается в перестановке ровно один раз). Вы хотите разбить ее на несколько последовательных подмассивов (возможно, всего один) так, чтобы число нечетных подмассивов среди них было как можно больше.
Какое наибольшее число этих подмассивов может быть нечетным?
Выходные данные
Для каждого набора входных данных выведите одно целое число — наибольшее возможное количество нечетных подмассивов, которое можно получить после разбиения перестановки на несколько последовательных подмассивов.
Примечание
В первом и третьем наборах входных данных, независимо от того, как мы разобьём нашу перестановку, не будет ни одного нечетного подмассива.
Во втором наборе входных данных мы можем разбить нашу перестановку на подмассивы \([4, 3], [2, 1]\), оба из которых нечетные, так как число инверсий в них равно \(1\).
В четвертом наборе входных данных мы можем разбить нашу перестановку на один подмассив \([2, 1]\), который является нечетным.
В пятом наборе входных данных мы можем разбить нашу перестановку на подмассивы \([4, 5], [6, 1, 2, 3]\). Первый подмассив имеет \(0\) инверсий, а второй — \(3\), поэтому он нечетный.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
1 2 3
4
4 3 2 1
2
1 2
2
2 1
6
4 5 6 1 2 3
|
0
2
0
1
1
|