B. Нечетные подмассивы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для массива $$$[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$$$ (каждое из них встречается в перестановке ровно один раз). Вы хотите разбить ее на несколько последовательных подмассивов (возможно, всего один) так, чтобы число нечетных подмассивов среди них было как можно больше.

Какое наибольшее число этих подмассивов может быть нечетным?

Входные данные

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$)  — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$)  — размер перестановки.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, все $$$p_i$$$ различны)  — элементы перестановки.

Сумма $$$n$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число  — наибольшее возможное количество нечетных подмассивов, которое можно получить после разбиения перестановки на несколько последовательных подмассивов.

Пример
Входные данные
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
Примечание

В первом и третьем наборах входных данных, независимо от того, как мы разобьём нашу перестановку, не будет ни одного нечетного подмассива.

Во втором наборе входных данных мы можем разбить нашу перестановку на подмассивы $$$[4, 3], [2, 1]$$$, оба из которых нечетные, так как число инверсий в них равно $$$1$$$.

В четвертом наборе входных данных мы можем разбить нашу перестановку на один подмассив $$$[2, 1]$$$, который является нечетным.

В пятом наборе входных данных мы можем разбить нашу перестановку на подмассивы $$$[4, 5], [6, 1, 2, 3]$$$. Первый подмассив имеет $$$0$$$ инверсий, а второй  — $$$3$$$, поэтому он нечетный.