题目描述

Suppose you have two points p=(xp,yp) and q=(xq,yq). Let's denote the Manhattan distance between them as d(p,q)=|xp−xq|+|yp−yq|.

Let's say that three points p, q, r form a bad triple if d(p,r)=d(p,q)+d(q,r).

Let's say that an array b1,b2,…,bm is good if it is impossible to choose three distinct indices i, j, k such that the points (bi,i), (bj,j) and (bk,k) form a bad triple.

You are given an array a1,a2,…,an. Calculate the number of good subarrays of a. A subarray of the array a is the array al,al+1,…,ar for some 1 $\\le$ l $\\le$ r $\\le$ n.

Note that, according to the definition, subarrays of length 1 and 2 are good.

输入格式

The first line contains one integer $t$ (1 $\\le$ t $\\le$ 5000) — the number of test cases.

The first line of each test case contains one integer $n$ ( 1 $\\le$ n $\\le$ $2 \\cdot 10^5$) — the length of array a.

The second line of each test case contains $n$ integers a1,a2,…,an (1 $\\le$ ai $\\le$ $1 \\cdot 10^9$).

It's guaranteed that the sum of $n$ doesn't exceed $2\\cdot10^5$ .

输出格式

For each test case, print the number of good subarrays of array a.

样例

3 
4 
2 4 1 3 
5 
6 9 1 9 6 
2 
13 37 

10 
12 
3 

提示

In the first test case, it can be proven that any subarray of a is good. For example, subarray [a2,a3,a4] is good since it contains only three elements and:

d((a2,2),(a4,4))=|4−3|+|2−4|=3 < d((a2,2),(a3,3))+d((a3,3),(a4,4))=3+1+2+1=7; d((a2,2),(a3,3)) < d((a2,2),(a4,4))+d((a4,4),(a3,3)); d((a3,3),(a4,4)) < d((a3,3),(a2,2))+d((a2,2),(a4,4)); In the second test case, for example, subarray [a1,a2,a3,a4] is not good, since it contains a bad triple (a1,1), (a2,2), (a4,4):

d((a1,1),(a4,4))=|6−9|+|1−4|=6; d((a1,1),(a2,2))=|6−9|+|1−2|=4; d((a2,2),(a4,4))=|9−9|+|2−4|=2; So, d((a1,1),(a4,4))=d((a1,1),(a2,2))+d((a2,2),(a4,4)).

来自Educational Codeforces Round 111 (Rated for Div. 2)

by 数据科学20-1 李伟杰