← 返回题目列表

Codeforces · 2222/C

C. 中位数分区

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

给你一个数组 $$$a$$$ ,其中 奇数 长度 $$$n$$$ 由正整数组成。您需要将序列划分为多个子数组$$$^{\text{*}}$$$ 奇数 长度和相同的中位数$$$^{\text{†}}$$$。你的任务是找到子数组的最大数量。

更正式地说,您需要找到一个长度为 $$$(p+1)$$$ 的严格递增序列 $$$k$$$,其中 $$$k_1=1$$$ 和 $$$k_{p+1}=n+1$$$,这样对于每个 $$$1\le i\le p$$$,序列的中位数$$$[a_{k_i},a_{k_i+1},\ldots,a_{k_{i+1}-1}]$$$ 都是相同的。 $$$k_i$$$ 和 $$$k_{i+1}$$$ 的奇偶校验应该不同。您的任务是找到 $$$p$$$ 的最大可能值。

$$$^{\text{*}}$$$数组 $$$b$$$ 是数组 $$$a$$$ 的子数组,如果 $$$b$$$ 可以通过从 $$$a$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。

$$$^{\text{†}}$$$奇数长度数组 $$$x$$$ 的中位数是数组按非降序排序后的第 $$$\lceil\frac{x}{2}\rceil$$$ 个元素。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n \lt 5000$$$,$$$n$$$ 是奇数) - $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le 10^9$$$) — $$$a$$$ 的元素。

保证所有测试用例的$$$n^2$$$总和不超过$$$5000^2$$$。

输出

对于每个测试用例,输出一个整数 - 子数组的最大数量。

示例

输入
复制

10
5
3 3 2 4 3
7
9 5 7 7 4 7 7
9
1 1 1 1 1 1 1 1 1
1
5
3
1 2 3
3
2 2 2
5
1 2 3 4 5
5
2 1 3 2 2
7
2 2 1 2 3 2 2
9
2 1 2 3 2 1 2 3 2

输出
复制

3
3
9
1
1
3
1
3
5
5

注意

在第一个测试用例中,最好将 $$$a$$$ 划分为 $$$[\underline 3, \underline 3, \underline{2, 4, 3}]$$$。

在第二个测试用例中,最好将 $$$a$$$ 划分为 $$$[\underline{9, 5, 7}, \underline 7, \underline{4, 7, 7}]$$$。

在第三个测试用例中,由于所有元素都相同,因此您可以将每个元素划分为单独的子数组。