在大法师学院，有一个特殊的传统：每位毕业生都必须完美掌握对魔法球进行排序的仪式。

在一个长祭坛上，从左到右放置着 $n$ 个球，每个球都有编号。每个球都有给定的强度，为了成功完成仪式，它们必须按照强度非降序排列。为了达到这个目的，可以交换球，在一次操作中，可以交换任意两个球。

然而，位置 $i$ 和 $j$ 之间的魔法流动是不稳定的，交换这两个位置上的球需要消耗 $(i - j - 2)^2$ 单位的法力值。

当球按正确的顺序排列时，仪式被视为完成。你需要以总法力消耗最小化的方式进行仪式。

你需要回答关于进行仪式的若干个独立询问。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 2 \cdot 10^5$) —— 仪式的数量。

接下来是仪式的描述。

每个仪式的第一行包含一个数字 $n$ ($1 \le n \le 2 \cdot 10^5$) —— 球的数量。

第二行给出 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) —— 每个球的强度。

保证所有仪式中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个仪式，输出一个整数 —— 完成仪式所需的最小法力消耗。

样例

输入样例 1

3
3
3 2 1
3
2 1 2
4
4 3 2 1

输出样例 1

0
1
2