The distance of a value $x$ in an array $c$, denoted as $d_x(c)$, is defined as the largest gap between any two occurrences of $x$ in $c$.

Formally, $d_x(c) = \max(j - i)$ over all pairs $i \lt j$ where $c_i = c_j = x$. If $x$ appears only once or not at all in $c$, then $d_x(c) = 0$.

The beauty of an array is the sum of the distances of each distinct value in the array. Formally, the beauty of an array $c$ is equal to $\sum\limits_{1\le x\le n} d_x(c)$.

Given an array $a$ of length $n$, an array $b$ is nice if it also has length $n$ and its elements satisfy $1\le b_i\le a_i$ for all $1\le i\le n$. Your task is to find the maximum possible beauty of any nice array.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1\le n\le 2\cdot10^5$) — the length of array $a$.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le n$) — the elements of array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.

Output

For each test case, output a single integer representing the maximum possible beauty among all nice arrays.

Note

In the first test case, if $b = [1, 2, 1, 2]$, then $d_1(b) = 3 - 1 = 2$ and $d_2(b) = 4 - 2 = 2$, resulting in a beauty of $2 + 2 = 4$. It can be proven that there are no nice arrays with a beauty greater than $4$.

In the second test case, both $b = [1, 1]$ and $b = [2, 2]$ are valid solutions with a beauty of $1$.

In the third test case, if $b = [1, 2, 1, 4, 1, 2, 1, 1, 1, 2]$ with $d_1(b) = 9 - 1 = 8$, $d_2(b) = 10 - 2 = 8$, and $d_4(b) = 0$, resulting in a beauty of $16$.