Median Witness - Repovive Standard Round 4 | 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$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

11E. Median Witness

Constraints

Input

Output

Samples

11E. Median Witness

Constraints

Input

Output

Samples