J. Reverse Inversion
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

$$$tarjen$$$ has a permutation $$$p$$$ of length $$$n$$$. You may perform at most one operation: choose two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) and reverse the subarray $$$p_l, p_{l+1}, \ldots, p_r$$$.

What is the maximum number of inversions in the permutation after the operation?

An inversion is a pair of indices $$$(i, j)$$$ satisfying $$$1 \le i \lt j \le n$$$ and $$$p_i \gt p_j$$$.

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 10^5$$$) — the number of test cases.

Each test case:

  • The first line contains an integer $$$n$$$ ($$$1 \le n \le 8000$$$) — the length of the permutation.
  • The second line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — the permutation.

The sum of $$$n$$$ over all test cases does not exceed $$$8000$$$.

Output

For each test case, output a single integer — the maximum number of inversions.

Example
Input
3
3
2 1 3
5
5 4 3 2 1
6
3 5 1 4 2 6
Output
2
10
10
Note

Reversing the interval $$$[1, 3]$$$ yields $$$[3, 1, 2]$$$, which has $$$2$$$ inversions: $$$(1,2)$$$ and $$$(1,3)$$$.