← 返回题目列表

Codeforces · 1529/B

B. Sifid 和奇怪的子序列

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

如果序列 $$$(b_1, b_2, \ldots, b_k)$$$ 的任意一对元素之间的绝对差大于或等于序列中的最大元素,则该序列称为奇怪序列。从形式上来说,如果对于每对 $$$(i, j)$$$ 和 $$$1 \le i<j \le k$$$,我们有 $$$|a_i-a_j|\geq MAX$$$,这很奇怪,其中 $$$MAX$$$ 是序列中最大的元素。特别是,任何长度最多 $$$1$$$ 的序列都是奇怪的。

例如,序列 $$$(-2021, -1, -1, -1)$$$ 和 $$$(-1, 0, 1)$$$ 很奇怪,但 $$$(3, 0, 1)$$$ 则不然,因为 $$$|0 - 1| < 3$$$。

Sifid 有一个由 $$$n$$$ 整数组成的数组 $$$a$$$。 Sifid 喜欢一切大的东西,所以在 $$$a$$$ 的所有奇怪子序列中,他想找到最长的子序列的长度。你能帮助他吗?

如果 $$$c$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$d$$$ 获得,则序列 $$$c$$$ 是数组 $$$d$$$ 的子序列。

输入

第一行包含一个整数 $$$t$$$ $$$(1\le t\le 10^4)$$$ — 测试用例的数量。测试用例的描述如下。

The first line of each test case contains an integer $$$n$$$ $$$(1\le n\le 10^5)$$$ — the length of the array $$$a$$$.

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ $$$(-10^9\le a_i \le 10^9)$$$ — 数组 $$$a$$$ 的元素。

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

输出

For each test case output a single integer — the length of the longest strange subsequence of $$$a$$$.

示例

输入 #1

6
4
-1 -2 0 0
7
-3 4 -2 0 -4 6 1
5
0 5 -3 2 -5
3
2 3 1
4
-3 0 2 0
6
-3 -2 -1 1 1 1

输出 #1

4
5
4
1
3
4

注意

In the first test case, one of the longest strange subsequences is $$$(a_1, a_2, a_3, a_4)$$$

In the second test case, one of the longest strange subsequences is $$$(a_1, a_3, a_4, a_5, a_7)$$$.

在第三个测试用例中,最长的奇怪子序列之一是 $$$(a_1, a_3, a_4, a_5)$$$。

在第四个测试用例中,最长的奇怪子序列之一是 $$$(a_2)$$$。

In the fifth test case, one of the longest strange subsequences is $$$(a_1, a_2, a_4)$$$.