Odd Subarrays

题意翻译

一个“奇怪”的序列满足此序列中有奇数个逆序对（满足 $a_i>a_j$ 且 $i<j$ 的 $(i,j)$ 称为逆序对） 现在你有一个序列 $p_1,p_2,\cdots,p_n$，你要把它**连续**地分为若干个子序列（可以只有 $1$ 个），你要使得这些子序列中“奇怪”的序列数最多。

题目描述

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?

输入输出格式

输入格式

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

输出格式

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.

输入输出样例

输入样例 #1

5
3
1 2 3
4
4 3 2 1
2
1 2
2
2 1
6
4 5 6 1 2 3

输出样例 #1

0
2
0
1
1

说明

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.

**题目大意：**

题目定义了一个“奇怪”的序列为含有奇数个逆序对的序列。逆序对是指满足 $a_i > a_j$ 且 $i < j$ 的数对 $(i, j)$。

给定一个序列 $p_1, p_2, \cdots, p_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$。

**输出格式：**
- 对于每个测试用例，输出一个整数，表示通过将排列分割成若干个连续子序列后，可以得到的最多的“奇怪”子序列的数量。

**输入输出样例：**

**输入样例 #1：**
```
5
3
1 2 3
4
4 3 2 1
2
1 2
2
2 1
6
4 5 6 1 2 3
```

**输出样例 #1：**
```
0
2
0
1
1
```

**说明：**
- 在前两个测试用例中，无论怎样分割排列，都不会产生“奇怪”的子序列。
- 在第三个测试用例中，可以将排列分割为子序列 $[4, 3], [2, 1]$，这两个子序列都含有1个逆序对，因此都是“奇怪”的。
- 在第四个测试用例中，可以将排列分割为单个子序列 $[2, 1]$，它是“奇怪”的。
- 在第五个测试用例中，可以将排列分割为子序列 $[4, 5], [6, 1, 2, 3]$。第一个子序列没有逆序对，第二个子序列有3个逆序对，因此是“奇怪”的。**题目大意：** 题目定义了一个“奇怪”的序列为含有奇数个逆序对的序列。逆序对是指满足 $a_i > a_j$ 且 $i < j$ 的数对 $(i, j)$。 给定一个序列 $p_1, p_2, \cdots, p_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$。 **输出格式：** - 对于每个测试用例，输出一个整数，表示通过将排列分割成若干个连续子序列后，可以得到的最多的“奇怪”子序列的数量。 **输入输出样例：** **输入样例 #1：** ``` 5 3 1 2 3 4 4 3 2 1 2 1 2 2 2 1 6 4 5 6 1 2 3 ``` **输出样例 #1：** ``` 0 2 0 1 1 ``` **说明：** - 在前两个测试用例中，无论怎样分割排列，都不会产生“奇怪”的子序列。 - 在第三个测试用例中，可以将排列分割为子序列 $[4, 3], [2, 1]$，这两个子序列都含有1个逆序对，因此都是“奇怪”的。 - 在第四个测试用例中，可以将排列分割为单个子序列 $[2, 1]$，它是“奇怪”的。 - 在第五个测试用例中，可以将排列分割为子序列 $[4, 5], [6, 1, 2, 3]$。第一个子序列没有逆序对，第二个子序列有3个逆序对，因此是“奇怪”的。