CF2222C Median Partition

给定一个长度为奇数 $n$ 的正整数数组 $a$。你需要将该序列划分为若干长度为奇数且中位数相同的子数组。你的任务是找到最多能划分出多少个这样的子数组。 更正式地说，你需要找到一个长度为 $(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$ 的最大可能值。 ∗ 一个数组 $b$ 是数组 $a$ 的子数组，如果 $b$ 可以通过删去 $a$ 开头的若干元素和结尾的若干元素（可以为零或全部）得到。 † 一个长度为奇数 $x$ 的数组的中位数是将其按非递减顺序排序后第 $\lceil\frac{x}{2}\rceil$ 个元素。

每组测试包含多组测试数据。第一行为测试组数 $t$（$1 \le t \le 1000$）。每组测试数据描述如下： 每组测试数据的第一行为一个整数 $n$（$1 \le n < 5000$，$n$ 是奇数），表示数组 $a$ 的长度。 第二行为 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示数组 $a$ 的每个元素。 保证所有测试用例的 $n^2$ 之和不超过 $5000^2$。

对于每组测试数据，输出一个整数，表示最多能划分出的子数组个数。

在第一个测试用例中，最优划分方式是 $[\underline 3, \underline 3, \underline{2, 4, 3}]$。 在第二个测试用例中，最优划分方式是 $[\underline{9, 5, 7}, \underline 7, \underline{4, 7, 7}]$。 在第三个测试用例中，因为所有元素都相同，你可以将每一个元素单独划分为一个子数组。 由 ChatGPT 5 翻译