CF1686B.Odd Subarrays

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 \lt j \le m$ and $b_i \gt 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?

对于数组 $[b_1, b_2, \ldots, b_m]$，定义其逆序对数为满足 $1 \le i \lt j \le m$ 且 $b_i \gt b_j$ 的整数对 $(i, j)$ 的个数。若一个数组 $b$ 的逆序对数为奇数，则称该数组为奇数组。

例如，数组 $[4, 2, 7]$ 是奇数组，因为其逆序对数为 $1$；而数组 $[2, 1, 4, 3]$ 不是奇数组，因为其逆序对数为 $2$。

给定一个 $1$ 到 $n$ 的排列 $[p_1, p_2, \ldots, p_n]$（其中每个整数恰好出现一次）。你需要将它划分为若干个连续子数组（可能仅一个），使得其中奇数组的个数尽可能多。

这些子数组中，最多可能有多少个是奇数组？

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$.

输入的第一行包含一个整数 $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$。

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.

对于每个测试用例，输出一个整数——将该排列分割为若干个连续子数组后，所能得到的奇数子数组的最大可能数量。

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.

在第一和第三个测试用例中，无论我们如何划分该排列，都不会存在奇子数组。

在第二个测试用例中，我们可以将该排列划分为子数组 $[4, 3], [2, 1]$，这两个子数组均为奇子数组，因为它们各自的逆序对数量均为 $1$。

在第四个测试用例中，我们可以将该排列划分为单个子数组 $[2, 1]$，该子数组为奇子数组。

在第五个测试用例中，我们可以将该排列划分为子数组 $[4, 5], [6, 1, 2, 3]$。第一个子数组有 $0$ 个逆序对，第二个子数组有 $3$ 个逆序对，因此它是奇子数组。