← 返回题目列表

Codeforces · 1832/C

C. 对比度值

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

对于整数数组 $$$[a_1, a_2, \dots, a_n]$$$,我们将值 $$$|a_1-a_2|+|a_2-a_3|+\cdots+|a_{n-1}-a_n|$$$ 称为数组的对比度。请注意,大小为 $$$1$$$ 的数组的对比度等于 $$$0$$$。

给你一个整数数组$$$a$$$。您的任务是构建一个 $$$b$$$ 数组,以满足以下所有条件:

- $$$b$$$ 不为空,即至少有一个元素;
- $$$b$$$ 是 $$$a$$$ 的子序列,即 $$$b$$$ 可以通过从 $$$a$$$ 中删除一些元素(可能为零)来生成;
- $$$b$$$ 的对比度等于 $$$a$$$ 的对比度。

数组 $$$b$$$ 的最小可能大小是多少?

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — 数组 $$$a$$$ 的大小。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \cdot, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — 数组本身的元素。

所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 数组 $$$b$$$ 的最小可能大小。

示例

输入 #1

4
5
1 3 3 3 7
2
4 2
4
1 1 1 1
7
5 4 2 1 0 0 4

输出 #1

2
2
1
3