P16920 [JLCPC 2026] 翻转逆序对

$\mathit{tarjen}$ 有一个长度为 $n$ 的排列 $p$。你可以执行至多一次操作：选择两个整数 $l$ 和 $r$（$1 \le l \le r \le n$），将子数组 $p_l, p_{l+1}, \ldots, p_r$ 翻转。 聪明的 $\mathit{tarjen}$ 想考考你，操作后排列的最大逆序对数是多少？ > 逆序对定义为满足 $1 \le i < j \le n$ 且 $p_i > p_j$ 的下标对 $(i, j)$。

第一行有一个整数 $T$（$1 \le T \le 10^5$），表示数据组数。接下来 $T$ 段，每段描述一组数据。对于每组数据： - 第一行一个整数 $n$（$1 \le n \le 8000$）表示排列长度。 - 第二行 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$）表示给出的排列。 数据保证 $\sum n \le 8000$。

对于每组数据，输出一行一个整数，表示最大逆序对数。

第一组数据中，翻转区间 $[1, 3]$ 得到 $[3, 1, 2]$，有 $2$ 个逆序对：$(1,2)$ 和 $(1,3)$。 第二组数据中，可以不进行操作，原排列为 $[5,4,3,2,1]$，有 $10$ 个逆序对，这是长度为 $5$ 的排列能达到的最大逆序对数量。 第三组数据中，翻转区间 $[3, 6]$ 得到 $[3, 5, 6, 2, 4, 1]$，有 $10$ 个逆序对：$(1,4)$、$(1,6)$、$(2,4)$、$(2,5)$、$(2,6)$、$(3,4)$、$(3,5)$、$(3,6)$、$(4,6)$ 和 $(5,6)$。