Stable Pairs - Repovive Opening Round | Repovive

0B. Stable Pairs

1000 pts2s256 MB

Given an array $a$ of $n$ distinct positive integers.

A pair of indices $(i, j)$ with $i < j$ is called stable if:

$1.$ $a_i < a_j$ (the pair is increasing), AND

$2.$ There is no index $k$ with $i < k < j$ such that $a_i < a_k < a_j$

In other words, a stable pair is an increasing pair where no element strictly between positions $i$ and $j$ has a value strictly between $a_i$ and $a_j$ .

Count the number of stable pairs.

Constraints

$1 \le t \le 5000$
$1 \le n \le 5000$
$1 \le a_i \le 10^9$
All elements in each test case are distinct.
The sum of $n$ over all test cases does not exceed $5000$ .

Input

t \\[0.5em] \left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

Output

\begin{array}{l} ans_1 \\ ans_2 \\ \vdots \\ ans_t \end{array}

Samples

Input

Explanation

Sample tests: mixed array, sorted ascending, sorted descending, alternating pattern.

Output

Given an array $a$ of $n$ distinct positive integers.

A pair of indices $(i, j)$ with $i < j$ is called stable if:

$1.$ $a_i < a_j$ (the pair is increasing), AND

$2.$ There is no index $k$ with $i < k < j$ such that $a_i < a_k < a_j$

In other words, a stable pair is an increasing pair where no element strictly between positions $i$ and $j$ has a value strictly between $a_i$ and $a_j$ .

Count the number of stable pairs.

Constraints

$1 \le t \le 5000$
$1 \le n \le 5000$
$1 \le a_i \le 10^9$
All elements in each test case are distinct.
The sum of $n$ over all test cases does not exceed $5000$ .

t \\[0.5em] \left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

\begin{array}{l} ans_1 \\ ans_2 \\ \vdots \\ ans_t \end{array}

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

0B. Stable Pairs

Input

Output

Samples

0B. Stable Pairs

Constraints

Input

Output

Samples

Constraints