Counting

Problem Description

For two points $P(x_0, y_0)$ and $Q(x_1, y_1)$ on the plane, the Manhattan distance between them is $d(P, Q) = |x_0 - x_1| + |y_0 - y_1|$.

A triple of points $p, q, r$ is called bad if and only if $d(p, r) = d(p, q) + d(q, r)$.

A sequence $a$ is called good if and only if you cannot choose three distinct indices $i, j, k$ from $a$ such that $(a_i, i), (a_j, j), (a_k, k)$ form a bad triple.

You are given a sequence $a$ of length $n$. How many subsegments of $a$ are good?

Input Format

The first line contains an integer $T$ ($1 \le T \le 5000$), the number of test cases.

For each test case:

The first line contains an integer $n$ ($1 \le n \le 2 \times 10^5$), the length of $a$.

The second line contains the sequence $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$).

Output Format

Output one number: the number of good subsegments of $a$.

Sample Input

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

Sample Output

10
12
3

Sample Explanation

In the first sample, no subsegment is bad, so $ans = 4 + 3 + 2 + 1 = 10$.

In the second sample, $1, 2, 4$ is bad, because

$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$

so $d((a_1, 1), (a_4, 4)) = d((a_1, 1), (a_2, 2)) + d((a_2, 2), (a_4, 4))$.