CF1682C LIS or Reverse LIS?

给定一个长度为 $n$ 的正整数数组 $a$。 记 $\text{LIS}(a)$ 表示数组 $a$ 的[最长严格递增子序列](https://en.wikipedia.org/wiki/Longest_increasing_subsequence)的长度。例如： - $\text{LIS}([2, \underline{1}, 1, \underline{3}]) = 2$。 - $\text{LIS}([\underline{3}, \underline{5}, \underline{10}, \underline{20}]) = 4$。 - $\text{LIS}([3, \underline{1}, \underline{2}, \underline{4}]) = 3$。 定义数组 $a'$ 为 $a$ 反转后的数组，即 $a' = [a_n, a_{n-1}, \ldots, a_1]$。 数组 $a$ 的美丽值定义为 $min(\text{LIS}(a), \text{LIS}(a'))$。 你的任务是，在可以任意重排数组 $a$ 的前提下，求出数组 $a$ 的最大可能美丽值。

输入包含多组测试数据。第一行包含一个整数 $t$ $(1 \leq t \leq 10^4)$，表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$ $(1 \leq n \leq 2 \cdot 10^5)$，表示数组 $a$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 10^9)$，表示数组 $a$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示任意重排后数组 $a$ 的最大可能美丽值。

在第一个测试用例中，$a = [6, 6, 6]$，$a' = [6, 6, 6]$，$\text{LIS}(a) = \text{LIS}(a') = 1$，因此美丽值为 $min(1, 1) = 1$。 在第二个测试用例中，$a$ 可以重排为 $[2, 5, 4, 5, 4, 2]$，此时 $a' = [2, 4, 5, 4, 5, 2]$，$\text{LIS}(a) = \text{LIS}(a') = 3$，因此美丽值为 $3$，且可以证明这是最大可能的美丽值。 在第三个测试用例中，$a$ 可以重排为 $[1, 2, 3, 2]$，此时 $a' = [2, 3, 2, 1]$，$\text{LIS}(a) = 3$，$\text{LIS}(a') = 2$，因此美丽值为 $min(3, 2) = 2$，且可以证明 $2$ 是最大可能的美丽值。 由 ChatGPT 4.1 翻译