给你一个数组 $$$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$$$。
输出
对于每个测试用例,输出一个整数 - 子数组的最大数量。
示例
输入复制
1053 3 2 4 379 5 7 7 4 7 791 1 1 1 1 1 1 1 11531 2 332 2 251 2 3 4 552 1 3 2 272 2 1 2 3 2 292 1 2 3 2 1 2 3 2
输出复制
3391131355
注意
在第一个测试用例中,最好将 $$$a$$$ 划分为 $$$[\underline 3, \underline 3, \underline{2, 4, 3}]$$$。
在第二个测试用例中,最好将 $$$a$$$ 划分为 $$$[\underline{9, 5, 7}, \underline 7, \underline{4, 7, 7}]$$$。
在第三个测试用例中,由于所有元素都相同,因此您可以将每个元素划分为单独的子数组。