数数

题目描述

对于平面上的两个点 $P(x_0,y_0)$，$Q(x_1,y_1)$，两点之间的曼哈顿距离为 $d(P,Q)=|x_0-x_1|+|y_0-y_1|$。

定义一组点 $p, q, r$ 为坏的当且仅当 $d(p,r)=d(p,q)+d(q,r)$。

定义一个序列 $a$ 是好的，当且仅当从 $a$ 中无法选出一组互不相同的数 $i, j, k$，使得 $(a_i,i), (a_j, j), (a_k, k)$ 是坏的。

给定了一个长度为 $n$ 的序列 $a$，请问 $a$ 中有多少个子段是好的。

输入格式

第一行给出一个 $T$ $(1\le T\le 5000)$，表示有 $T$ 组数据

接下来对于每一组数据：

第一行给出一个数 $n$ $(1\le n\le 2 * 10^5)$，表示 $a$ 的长度

第二行给出序列 $a_1$，$a_2$，... $a_n$ $(0\le a_i\le 10^9)$

输出格式

输出一个数表示 $a$ 中好子段的个数

样例输入

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

样例输出

10
12
3

样例解释

第一个样例没有一个子段是坏的，所以 $ans=4+3+2+1=10$

第二个样例中，$1, 2, 4$ 是坏的，因为

$d((a_1,1),(a_4,4))=|6-9|+|1-4|=6$

$d((a_1,1),(a_2,2))=|6-9|+|1-2|=4$

$d((a_2,2),(a_4,4))=|9-9|+|2-4|=2$

所以 $d((a_1,1),(a_4,4))=d((a_1,1),(a_2,2))+d((a_2,2),(a_4,4))$