Let $X = x_1, x_2, \dots, x_n$ be a permutation of the positive integers $1, 2, \dots, n$. An inversion pair $(i, j)$ of $X$ is defined as $i < j$ and $x_i > x_j$. The total number of inversion pairs in $X$ is called the inversion number of $X$, denoted by $\delta(X)$. The $n$ cyclic shifts of $X$, denoted by $\text{shift}(j)$ for $0 \le j \le n-1$, are defined as $\text{shift}(j) = x_{j+1}, \dots, x_n, x_1, \dots, x_j$. The cyclic permutation problem is to calculate $\min_{0 \le j < n} \{\delta(\text{shift}(j))\}$ for a given permutation $X$.
For example, when $n=10$ and $X = 1, 7, 10, 2, 3, 8, 4, 5, 9, 6$, $\min_{0 \le j < n} \{\delta(\text{shift}(j))\} = 13$.
Implementation Details
Given a permutation $X = x_1, x_2, \dots, x_n$ of the positive integers $1, 2, \dots, n$, calculate $\min_{0 \le j < n} \{\delta(\text{shift}(j))\}$.
Input
The input contains $k$ ($1 \le k \le 300$) test cases. The first line of each test case contains a positive integer $n$ ($1 \le n \le 5000$), representing the length of the given permutation $X = x_1, x_2, \dots, x_n$. The next line contains $n$ positive integers, representing $x_1, x_2, \dots, x_n$.
- For 20% of the test data, $n \le 500$.
- For 30% of the test data, $n \le 1500$.
- For 100% of the test data, $n \le 5000$.
Output
For each test case, output the calculated minimum inversion number on a new line.
Examples
Input 1
10 1 7 10 2 3 8 4 5 9 6 10 1 7 10 2 3 8 6 4 5 9
Output 1
13 14