406829: GYM102566 F Magic Wand

You have been captured by a group of magic wizards and they will not let you go unless you solve their puzzle.

You are given an array $$$A$$$ of $$$N \leq 10^5$$$ integers, $$$0 \leq A_i \leq 10^9$$$ that you need to sort in non-decreasing order. Because it is part of the magic realm, the only way you can manipulate it is using a magic wand that you were given.

The wand allows you to pick a contiguous subsequence of integers $$$A[i...j]$$$ and sort it, consuming $$$(j - i + 1)^3$$$ energy in the process.

Because you don't know how much energy the wand initially contains, you have to find the minimum amount you need to sort the entire array.

The first line of the input will contain the number $$$T$$$, representing the number of test cases.

The first line of each test will contain one positive integer: $$$N$$$

It is guaranteed that among all test cases $$$\sum N \leq 2* 10^6$$$.

The second line of each test case will contain $$$N$$$ integers, the initial configuration of the array.

For each testcase, you should output one line containing one integer: the minimum amount of energy required to sort the array using the wand.

1
4
2 1 4 3

16

The first move is $$$[1..2]$$$ with cost $$$(2-1+1)^3 = 8$$$. The new array is 1 2 4 3.

The second move is $$$[3..4]$$$ with cost $$$(4-3+1)^3 = 8$$$. The new array is 1 2 3 4, which is sorted.

It can be shown that 16 is the minimum cost for this array.