27B. Maximum Swap Score

1000 pts2s256 MB

You are given a permutation $p_1,p_2,\ldots,p_n$ of the integers from $1$ to $n$ . Your score is initially $0$ .

In one move, choose two indices $i<j$ such that $p_i>p_j$ , swap $p_i$ and $p_j$ , and add $j-i$ to your score.

You may perform any number of moves, including zero. Find the maximum total score you can obtain.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le p_i \le n$
All values $p_1,p_2,\ldots,p_n$ are distinct.
The sum of $n$ over all test cases is at most $2 \times 10^5$ .

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} \mathrm{answer} \end{array} \right\} \times t

For each test case, print one integer: the maximum total score you can obtain.

Samples

Input

Case 1

1
1

Case 2

3
3 2 1

Case 3

5
2 5 1 4 3

Explanation

Case 1

There are no two indices to choose, so no move is possible and the score remains 0.

Case 2

Starting from [3, 2, 1], swap positions 1 and 2 to obtain [2, 3, 1] and gain 1 point. Then swap positions 1 and 3 to obtain [1, 3, 2] and gain 2 points. Finally, swap positions 2 and 3 to obtain [1, 2, 3] and gain 1 point. The total score is 4, which is the maximum possible.

Case 3

Swap the following pairs of positions in order: (1, 3), (4, 5), (2, 5), (2, 4), and (2, 3). The resulting permutations are [1, 5, 2, 4, 3], [1, 5, 2, 3, 4], [1, 4, 2, 3, 5], [1, 3, 2, 4, 5], and [1, 2, 3, 4, 5]. Every move is allowed, and the total score is 2 + 1 + 3 + 2 + 1 = 9. No sequence of moves gives a larger score.

Output

Case 1

Case 2

Case 3

Input

Case 1

2
1 2

Case 2

2
2 1

Case 3

3
2 3 1

Explanation

Case 1

The permutation is already sorted, so no move is possible.

Case 2

Swap positions 1 and 2 to gain 1 point. The permutation then becomes [1, 2], and no further move is possible.

Case 3

Swap positions 1 and 3 to obtain [1, 3, 2] and gain 2 points. Then swap positions 2 and 3 to obtain [1, 2, 3] and gain 1 point. The maximum total score is 3.

Output

Case 1

Case 2

Case 3

Input

Case 1

3
3 2 1

Case 2

1
1

Case 3

2
1 2

Explanation

Case 1

Case 2

There are no two indices to choose, so no move is possible and the score remains 0.

Case 3

The permutation is already sorted, so no move is possible.

Output

Case 1

Case 2

Case 3

You are given a permutation $p_1,p_2,\ldots,p_n$ of the integers from $1$ to $n$ . Your score is initially $0$ .

In one move, choose two indices $i<j$ such that $p_i>p_j$ , swap $p_i$ and $p_j$ , and add $j-i$ to your score.

You may perform any number of moves, including zero. Find the maximum total score you can obtain.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le p_i \le n$
All values $p_1,p_2,\ldots,p_n$ are distinct.
The sum of $n$ over all test cases is at most $2 \times 10^5$ .

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} \mathrm{answer} \end{array} \right\} \times t

For each test case, print one integer: the maximum total score you can obtain.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

27B. Maximum Swap Score

Constraints

Input

Output

Samples

27B. Maximum Swap Score

Constraints

Input

Output

Samples