#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/11/problems/E

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

Median Witness - Repovive Standard Round 4 | Repovive | Repovive

11E. Median Witness

2500 pts2s256 MB

You are given a permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$ .

For a sequence of length $k$ , its median is defined as the $\left\lceil \frac{k}{2} \right\rceil$ -th smallest element of the sequence. In particular, for even $k$ , this is the lower median.

Count the number of pairs $(i,j)$ such that $1 \le i < j \le n$ and there exists an interval $[l,r]$ satisfying all of the following conditions:

$1 \le l \le i < j \le r \le n$
The median of $p_l, p_{l+1}, \ldots, p_r$ is at least $p_i$

For each test case, output this number.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 10^6$
$p_1, p_2, \ldots, p_n$ is a permutation of $1,2,\ldots,n$
The sum of $n$ over all test cases is at most $10^6$

Input

t

\left. \begin{array}{l} n \\ p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

1
1

Case 2

2
1 2

Case 3

2
2 1

Case 4

3
2 1 3

Case 5

4
3 1 4 2

Explanation

Case 1

There are no pairs of indices, so the answer is $0$ .

Case 2

The good pairs are $(1, 2)$ .

For $(1, 2)$ , choose $[l,r]=[1,2]$ . The sequence is $1,2$ , and its median is $1$ , which is at least $p_1=1$ .

Case 3

There are no good pairs.

The only pair is $(1, 2)$ . The only possible interval is $[1,2]$ . The sequence is $2,1$ , and its median is $1$ , which is smaller than $p_1=2$ .

Case 4

The good pairs are $(1, 2)$ , $(1, 3)$ , and $(2, 3)$ .

For $(1, 2)$ and $(1, 3)$ , choose $[l,r]=[1,3]$ . The sequence is $2,1,3$ , and its median is $2$ , which is at least $p_1=2$ .

For $(2, 3)$ , choose $[l,r]=[2,3]$ . The sequence is $1,3$ , and its median is $1$ , which is at least $p_2=1$ .

Case 5

The good pairs are $(1, 2)$ , $(1, 3)$ , $(2, 3)$ , and $(2, 4)$ .

For $(1, 2)$ and $(1, 3)$ , choose $[l,r]=[1,3]$ . The sequence is $3,1,4$ , and its median is $3$ , which is at least $p_1=3$ .

For $(2, 3)$ , choose $[l,r]=[2,3]$ . The sequence is $1,4$ , and its median is $1$ , which is at least $p_2=1$ .

For $(2, 4)$ , choose $[l,r]=[2,4]$ . The sequence is $1,4,2$ , and its median is $2$ , which is at least $p_2=1$ .

Output

Case 1

Case 2

Case 3

Case 4

Case 5

You are given a permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$ .

For a sequence of length $k$ , its median is defined as the $\left\lceil \frac{k}{2} \right\rceil$ -th smallest element of the sequence. In particular, for even $k$ , this is the lower median.

Count the number of pairs $(i,j)$ such that $1 \le i < j \le n$ and there exists an interval $[l,r]$ satisfying all of the following conditions:

$1 \le l \le i < j \le r \le n$
The median of $p_l, p_{l+1}, \ldots, p_r$ is at least $p_i$

For each test case, output this number.

$1 \le t \le 10^4$
$1 \le n \le 10^6$
$p_1, p_2, \ldots, p_n$ is a permutation of $1,2,\ldots,n$
The sum of $n$ over all test cases is at most $10^6$

t

\left. \begin{array}{l} n \\ p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

There are no pairs of indices, so the answer is $0$ .

The good pairs are $(1, 2)$ .

For $(1, 2)$ , choose $[l,r]=[1,2]$ . The sequence is $1,2$ , and its median is $1$ , which is at least $p_1=1$ .

There are no good pairs.

The only pair is $(1, 2)$ . The only possible interval is $[1,2]$ . The sequence is $2,1$ , and its median is $1$ , which is smaller than $p_1=2$ .

The good pairs are $(1, 2)$ , $(1, 3)$ , and $(2, 3)$ .

For $(1, 2)$ and $(1, 3)$ , choose $[l,r]=[1,3]$ . The sequence is $2,1,3$ , and its median is $2$ , which is at least $p_1=2$ .

For $(2, 3)$ , choose $[l,r]=[2,3]$ . The sequence is $1,3$ , and its median is $1$ , which is at least $p_2=1$ .

The good pairs are $(1, 2)$ , $(1, 3)$ , $(2, 3)$ , and $(2, 4)$ .

For $(1, 2)$ and $(1, 3)$ , choose $[l,r]=[1,3]$ . The sequence is $3,1,4$ , and its median is $3$ , which is at least $p_1=3$ .

For $(2, 3)$ , choose $[l,r]=[2,3]$ . The sequence is $1,4$ , and its median is $1$ , which is at least $p_2=1$ .

For $(2, 4)$ , choose $[l,r]=[2,4]$ . The sequence is $1,4,2$ , and its median is $2$ , which is at least $p_2=1$ .

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

11E. Median Witness

Constraints

Input

Output

Samples

11E. Median Witness

Constraints

Input

Output

Samples