题目描述

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

输出格式

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

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

2
10
10

提示

第一组数据中，翻转区间 $[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)$。