P15313 [VKOSHP 2025] Magic Ritual

在大法师学院，有一个特殊的传统：每位毕业生都必须完美掌握排序魔法球的仪式。 在一个长长的祭坛上，从左到右放置着 $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$。

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

翻译由 DeepSeek 完成