Problem Description

$\mathit{tarjen}$ has a permutation $p$ of length $n$. You may perform the following operation at most once: 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$.

The smart $\mathit{tarjen}$ wants to test you: what is the maximum number of inversions in the permutation after the operation?

An inversion is defined as a pair of indices $(i, j)$ such that $1 \le i < j \le n$ and $p_i > p_j$.

Input Format

The first line contains an integer $T$ ($1 \le T \le 10^5$), indicating the number of test cases. Then follow $T$ blocks, each describing one test case. For 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$), representing the given permutation.

The testdata guarantees that $\sum n \le 8000$.

Output Format

For each test case, output one integer per line, representing the maximum number of inversions.

3
3
2 1 3
5
5 4 3 2 1
6
3 5 1 4 2 6

2
10
10

Hint

In the first test case, reversing the interval $[1, 3]$ yields $[3, 1, 2]$, which has $2$ inversions: $(1,2)$ and $(1,3)$.

In the second test case, you may choose not to perform any operation. The original permutation is $[5,4,3,2,1]$, which has $10$ inversions. This is the maximum number of inversions achievable by a permutation of length $5$.

In the third test case, reversing the interval $[3, 6]$ yields $[3, 5, 6, 2, 4, 1]$, which has $10$ inversions: $(1,4)$, $(1,6)$, $(2,4)$, $(2,5)$, $(2,6)$, $(3,4)$, $(3,5)$, $(3,6)$, $(4,6)$, and $(5,6)$.

Translated by ChatGPT 5