Odd Subarrays
Contest: Codeforces Round 794 (Div. 2)
Difficulty rating: 800
Tags: dp, greedy

For an array $$$[b_1, b_2, \ldots, b_m]$$$ define its number of inversions as the number of pairs $$$(i, j)$$$ of integers such that $$$1 \le i < j \le m$$$ and $$$b_i>b_j$$$. Let's call array $$$b$$$ odd if its number of inversions is odd.

For example, array $$$[4, 2, 7]$$$ is odd, as its number of inversions is $$$1$$$, while array $$$[2, 1, 4, 3]$$$ isn't, as its number of inversions is $$$2$$$.

You are given a permutation $$$[p_1, p_2, \ldots, p_n]$$$ of integers from $$$1$$$ to $$$n$$$ (each of them appears exactly once in the permutation). You want to split it into several consecutive subarrays (maybe just one), so that the number of the odd subarrays among them is as large as possible.

What largest number of these subarrays may be odd?

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$)  — the size of the permutation.

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, all $$$p_i$$$ are distinct)  — the elements of the permutation.

The sum of $$$n$$$ over all test cases doesn't exceed $$$2\cdot 10^5$$$.

Output format:
For each test case output a single integer  — the largest possible number of odd subarrays that you can get after splitting the permutation into several consecutive subarrays.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first and third test cases, no matter how we split our permutation, there won't be any odd subarrays.

In the second test case, we can split our permutation into subarrays $$$[4, 3], [2, 1]$$$, both of which are odd since their numbers of inversions are $$$1$$$.

In the fourth test case, we can split our permutation into a single subarray $$$[2, 1]$$$, which is odd.

In the fifth test case, we can split our permutation into subarrays $$$[4, 5], [6, 1, 2, 3]$$$. The first subarray has $$$0$$$ inversions, and the second has $$$3$$$, so it is odd.

Example input:
5
3
1 2 3
4
4 3 2 1
2
1 2
2
2 1
6
4 5 6 1 2 3

Example output:
0
2
0
1
1

Editorial:
Consider any optimal splitting.
Clearly, for any subarray $$$[b_1, b_2, \ldots, b_m]$$$ which is not odd, we can just split it into $$$[b_1], [b_2], \ldots, [b_m]$$$,
For any odd subarray $$$[b_1, b_2, \ldots, b_m]$$$ with $$$m \ge 3$$$, there exists an $$$1 \le i \le m-1$$$ such that $$$b_i > b_{i+1}$$$ (otherwise $$$b$$$ is sorted and has no inversions). Then, we can split $$$b$$$ into $$$[b_1], [b_2], \ldots, [b_{i-1}], [b_i, b_{i+1}], [b_{i+2}], \ldots, [b_m]$$$, where we also have one odd subarray.
So, if we can split $$$p$$$ into several subarrays such that there are $$$k$$$ odd subarrays, we can split it into several subarrays of length $$$\le 2$$$ so that there are $$$k$$$ odd subarrays too. Then, let $$$dp_i$$$ denote the largest number of odd subarrays we can get from splitting $$$p[1:i]$$$. Then, $$$dp_i = max(dp_{i-1}, dp_{i-2} + (p_{i-1} > p_i))$$$. This $$$dp$$$ can be calculated in $$$O(n)$$$.
It's also easy to show that the following greedy algorithm works: traverse the permutation from left to right, whenever you see two elements $$$p_{i-1}>p_i$$$, make a subarray $$$[p_{i-1}, p_i]$$$, and proceed from $$$p_{i+1}$$$.