310429: CF1832C. Contrast Value
Description
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$?
InputThe 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$.
OutputFor each test case, print a single integer — the minimum possible size of the array $b$.
ExampleInput4 5 1 3 3 3 7 2 4 2 4 1 1 1 1 7 5 4 2 1 0 0 4Output
2 2 1 3
Input
题意翻译
定义序列 $a_1,a_2,\dots,a_n$ 的权值是 $|a_1-a_2|+|a_2-a_3|+\dots+|a_{n-1}-a_n|$。 $T$ 次询问，每次给一个序列 $a$ ，一个 $a$ 的子序列 $b$ 合法当且仅当 $b$ 权值和 $a$ 相等，求 $b$ 的最小长度。Output
对于一个整数数组 \([a_1, a_2, \dots, a_n]\)，定义数组的对比值为 \(\sum_{i=1}^{n-1} |a_i - a_{i+1}|\)。注意，对于大小为 1 的数组，其对比值等于 0。
给定一个整数数组 \(a\)，你的任务是构建一个数组 \(b\)，使得满足以下条件：
1. \(b\) 非空，即至少包含一个元素；
2. \(b\) 是 \(a\) 的子序列，即 \(b\) 可以通过删除 \(a\) 中的某些元素（可能为零个）得到；
3. \(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, \dots, a_n\) (\(0 \le a_i \le 10^9\)），表示数组 \(a\) 的元素。
- 所有测试用例的 \(n\) 之和不超过 \(3 \cdot 10^5\)。
输出：
- 对于每个测试用例，输出一个整数，表示数组 \(b\) 的最小可能大小。
示例：
输入：
```
4
5
1 3 3 3 7
2
4 2
4
1 1 1 1
7
5 4 2 1 0 0 4
```
输出：
```
2
2
1
3
```题目大意： 对于一个整数数组 \([a_1, a_2, \dots, a_n]\)，定义数组的对比值为 \(\sum_{i=1}^{n-1} |a_i - a_{i+1}|\)。注意，对于大小为 1 的数组，其对比值等于 0。 给定一个整数数组 \(a\)，你的任务是构建一个数组 \(b\)，使得满足以下条件： 1. \(b\) 非空，即至少包含一个元素； 2. \(b\) 是 \(a\) 的子序列，即 \(b\) 可以通过删除 \(a\) 中的某些元素（可能为零个）得到； 3. \(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, \dots, a_n\) (\(0 \le a_i \le 10^9\)），表示数组 \(a\) 的元素。 - 所有测试用例的 \(n\) 之和不超过 \(3 \cdot 10^5\)。 输出： - 对于每个测试用例，输出一个整数，表示数组 \(b\) 的最小可能大小。 示例： 输入： ``` 4 5 1 3 3 3 7 2 4 2 4 1 1 1 1 7 5 4 2 1 0 0 4 ``` 输出： ``` 2 2 1 3 ```