Darnassus

$\space \space$*Even the World Tree must bow to the cycle of life. Everything born will die.*

$\space \space$*Archimonde has hurt it once, Sylvanas burnt it again.*

$\space \space$*Now the World Tree is slowly recovering.*

The World Tree is burnt apart into $n$ parts. Now it tries to rebuild itself.

Each part of the World Tree has an attribute $p_i$, and all $p_i\ (1\leq i\leq n)$ forms a permutation of $1,2,3...n$.

For all $1 \leq i < j \leq n$, if the World Tree wants to grow an edge connecting part $i$ and part $j$ directly, it needs to spend $|i-j| * |p_i-p_j|$ energy. $|x|$ means the absolute value of $x$.

The World Tree is very smart, so it will grow some edges such that all its $n$ parts become connected (in other words, you can go from any part to any other part using only the edges that have been grown), spending the minimum energy.

Please calculate the minimum energy the World Tree needs to spend.

The input consists of multiple test cases.

The first line contains an integer $T\ (1\leq T \leq 5)$ denoting the number of test cases.

For each test case, the first line contains a single integer $n(1 \leq n \leq 50000)$.

The second line contains $n$ integers $p_i\ (1 \leq p_i \leq n)$, it's guaranteed that all $p_i$ forms a permutation.

For each test case, output one line containing one integer indicating the answer.

2
5
4 3 5 1 2
10
4 7 3 8 6 1 9 10 5 2

7
24

2022“杭电杯”中国大学生算法设计超级联赛（8）