C. Contrast Value
greedy; implementation
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\)?
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\).
For each test case, print a single integer — the minimum possible size of the array \(b\).