企业官网建设流程全解析

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; }