time limit per test
2 seconds
memory limit per test
256 megabytes
For an array of integers [a1,a2,…,an], let's call the value |a1−a2|+|a2−a3|+⋯+|an−1−an| 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?
Input
The first line contains a single integer t (1≤t≤104) — the number of test cases.
The first line of each test case contains a single integer n (1≤n≤3⋅105) — the size of the array a.
The second line contains n integers a1,a2,⋅,an (0≤ai≤109) — elements of the array itself.
The sum of n over all test cases doesn't exceed 3⋅105.
Output
For each test case, print a single integer — the minimum possible size of the array b.
Example
Input
Copy
4
5
1 3 3 3 7
2
4 2
4
1 1 1 1
7
5 4 2 1 0 0 4
Output
Copy
2 2 1 3
解题说明：此题是一道数学题，找规律可以发现数组元素分布最高点和最低点到两端的端点的绝对值之差与整个段的绝对值之差相等，因此只需要统计最低点和最高点的数目就行了。
#include <stdio.h> int a[300005]; int main() { int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } int ans = 1; for (int i = 2, op = 0; i <= n; i++) { if (a[i] > a[i - 1] && op != 1) { ans++; op = 1; } else if (a[i] < a[i - 1] && op != -1) { ans++; op = -1; } } printf("%d\n", ans); } return 0; }
