问题 J: 中位数

对于一个长度为 $L$ （$L$ 为奇数） 的数组 $a$，定义它的中位数 $\text{median}$（a） 为 $a$ 中第 L+122L+1 大的数。

现在给你一个长度为 $n$ 的排列，对于每对满足 $1\le i\le j\le n$ 且 $j-i\equiv 0(\mathrm{mod}2)$ 的 （$i$, $j$），你需要计算 $i\ast j\ast \text{median}$（$p[i\dots j]$）。

输出所有值的总和。

第一行输入一个整数 $T$ （$1\le T\le 20$），表示测试的总数。

对于每个测试用例，第一行输入一个整数 $n$（$1\le n\le 2000$）。

接来下一行 $n$ 个整数，表示 $1$ 到 $n$ 的排列。