P16920 [JLCPC 2026] Reverse Inversions

$\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$.

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$.

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

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