子序列问题

2S

题目描述

我们称一个长度为 $k$ 的整数序列 $C=(c_1,c_2,\dots,c_k)$ 是“好”的，当且仅当它的最小元素与最大元素的平均值恰好等于它的中位数。

对于一个长度为 $k$ 的序列，其中位数定义为：将序列从小到大排序后，第 $\lceil k/2\rceil$ 小的元素。其中 $\lceil x\rceil$ 表示不小于 $x$ 的最小整数。

例如：

• 序列 $1,7,4,3$ 的中位数是 $3$，因为排序后为 $1,3,4,7$；
• 序列 $5,8,2,1,6$ 的中位数是 $5$，因为排序后为 $1,2,5,6,8$。

形式化地说，设 $D=(d_1,d_2,\dots,d_k)$ 为 $C$ 排序后的序列，则 $C$ 是“好”的，当且仅当

现在给定一个整数序列 $A=(a_1,a_2,\dots,a_n)$，请你求出它的最长“好”子序列的长度。

子序列是指：通过删除原序列中的某些元素（也可以一个都不删），且不改变剩余元素相对顺序得到的新序列。

输入格式

输入包含多组测试数据。

从标准输入按以下格式读取数据：

$T$

$n$

$a_1$ $a_2$ $\dots$ $a_n$

其中：

• 第一行输入一个整数 $T$，表示测试数据组数。

• 对于每组测试数据：

  • 第一行输入一个整数 $n$，表示序列长度；
  • 第二行输入 $n$ 个整数 $a_i$，表示给定序列。

数据范围

• $1 \le T \le 10$
• $1 \le n \le 3 \times 10^3$
• $1 \le a_i \le 10^9$
• 保证所有测试数据中 $n$ 的总和不超过 $3 \times 10^4$

部分数据满足：

• $30$ 的数据满足：$n \le 20,\ a_i \le 100$
• $60$ 的数据满足：$n \le 100,\ a_i \le 10^3$
• $80$ 的数据满足：$n \le 1000$
• $100$ 的数据无特殊限制

输出格式

对于每组测试数据，输出一行一个整数，表示最长“好”子序列的长度。

样例

4
7
3 5 9 8 2 11 5
7
7 9 2 4 17 10 15
1
100
2
100 100

5
4
1
2

说明/提示

对于第一个样例，最长的“好”子序列是 $3,5,8,2,5$。其最小元素为 $2$，最大元素为 $8$，中位数为 $5$。

对于第二个样例，最长的“好”子序列是 $7,9,4,10$。其最小元素为 $4$，最大元素为 $10$，中位数为 $7$。