CF1832C.Contrast Value

For an array of integers $[a_1, a_2, \dots, a_n]$, let's call the value $|a_1-a_2|+|a_2-a_3|+\cdots+|a_{n-1}-a_n|$ the contrast of the array. Note that the contrast of an array of size $1$ is equal to $0$.

You are given an array of integers $a$. Your task is to build an array of $b$ in such a way that all the following conditions are met:

• $b$ is not empty, i.e there is at least one element;
• $b$ is a subsequence of $a$, i.e $b$ can be produced by deleting some elements from $a$ (maybe zero);
• the contrast of $b$ is equal to the contrast of $a$.

What is the minimum possible size of the array $b$?

对于一个整数数组 $[a_1, a_2, \dots, a_n]$，我们称其**对比度（contrast）**为值 $|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$ 的最小可能长度是多少？

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

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

The second line contains $n$ integers $a_1, a_2, \cdot, a_n$ ($0 \le a_i \le 10^9$) — elements of the array itself.

The sum of $n$ over all test cases doesn't exceed $3 \cdot 10^5$.

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

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

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^9$）—— 数组的元素。

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

For each test case, print a single integer — the minimum possible size of the array $b$.

对于每个测试用例，输出一个整数——数组 $b$ 的最小可能长度。