1832C.md (1427B)
1 Source: https://codeforces.com/problemset/problem/1832/C 2 3 C. Contrast Value 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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$. 22 23 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: 24 25 * $b$ is not empty, i.e there is at least one element; 26 * $b$ is a subsequence of $a$, i.e $b$ can be produced by deleting some elements from $a$ (maybe zero); 27 * the contrast of $b$ is equal to the contrast of $a$. 28 29 What is the minimum possible size of the array $b$? 30 31 Input 32 33 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 34 35 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$. 36 37 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. 38 39 The sum of $n$ over all test cases doesn't exceed $3 \cdot 10^5$. 40 41 Output 42 43 For each test case, print a single integer — the minimum possible size of the array $b$. 44 45 Example 46 47 Input 48 49 ``` 50 4 51 52 5 53 54 1 3 3 3 7 55 56 2 57 58 4 2 59 60 4 61 62 1 1 1 1 63 64 7 65 66 5 4 2 1 0 0 4 67 ``` 68 69 Output 70 71 ``` 72 2 73 2 74 1 75 3 76 ```