Description

At the Academy of Archmages, there is a special tradition: every graduate must master the ritual of sorting magical spheres perfectly.

On a long altar, there are $n$ spheres placed from left to right, each numbered. Each sphere has a given strength, and to successfully complete the ritual, they must be arranged in non-decreasing order of strength. To achieve this, spheres can be swapped, and in one action, any two spheres can be exchanged.

However, the magical flow between two positions $i$ and $j$ is unstable, and swapping the spheres at these positions requires spending $(i - j - 2)^2$ units of mana.

The ritual is considered complete when the spheres are arranged in the correct order. You need to conduct the ritual in such a way that the total mana expenditure is minimized.

You will need to answer several independent queries about conducting the rituals.

Input Format

The first line contains an integer $t$ ($1 \le t \le 2 \cdot 10^5$) --- the number of rituals.

The descriptions of the rituals follow.

In the first line of each ritual, there is a number $n$ ($1 \le n \le 2 \cdot 10^5$) --- the number of spheres.

In the second line, $n$ integers $a_1, a_2, \dots, a_n$ are given ($0 \le a_i \le 10^9$) --- the strength of each sphere.

It is guaranteed that the sum of $n$ across all rituals does not exceed $2 \cdot 10^5$.

Output Format

For each ritual, output a single integer --- the minimum mana expenditure to complete the ritual.

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

0
1
2