← 返回题目列表

Codeforces · 1686/B

B. 奇数子数组

中文机器翻译题面 查看原题

对于数组 $$$[b_1, b_2, \ldots, b_m]$$$,将其反转次数定义为满足 $$$1 \le i < j \le m$$$ 且 $$$b_i>b_j$$$ 的整数对 $$$(i, j)$$$ 的数量。如果数组 $$$b$$$ 的反转次数是奇数,我们称其为奇数。

例如,数组 $$$[4, 2, 7]$$$ 是奇数,因为它的反转次数是 $$$1$$$,而数组 $$$[2, 1, 4, 3]$$$ 不是奇数,因为它的反转次数是 $$$2$$$。

给你一个从 $$$1$$$ 到 $$$n$$$ 的整数排列 $$$[p_1, p_2, \ldots, 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]$$$。第一个子数组有 $$$0$$$ 反转,第二个子数组有 $$$3$$$,所以它是奇数。