Hizitizi's Array Cutting

Riaz_BSMRSTU Replay of BSMRSTU Home Qu...
Limits 1s, 512 MB

Hizitizi is a new character in our story. In every episode, he gets a task to do from his imaginary girlfriend (He made her on his mind). Today's task is to cut an array. As, she is imaginary, Hizitizi can do some cheating with her. He is now telling you to complete this task for him, so that he can spend all the day with his imaginary girlfriend.

You will be given an array of positive integer of n length. You have to split this array in three part so that.

  1. Every part is non-empty.
  2. If we take two index i and j (j > i), and

Suppose we have an array [1, 2, 3, 1, 2]. Now, we can split this array in 3 part [1, 2], [3], [1, 2], where sum of these three part is respectively 3, 3 and 3. Now, (3 - 3)2 + (3 - 3)2 = 0, which is minimum.

Input

Input will contain T (1 ≤ T ≤ 100) test cases.
Each case will contain two lines of input. First line will contain n (3 ≤ n ≤ 105), length of the array.
Next line will contain n integer (a1, a2 ... an), where (1 ≤ ai ≤ 104).

Note: Sum of n over all test cases won't be more than 106.

Output

Print the minimum value of (A - B)2 + (B - C)2.

Sample

InputOutput
1
5
1 2 3 1 2
0

Submit

Login to submit.

Statistics

61% Solution Ratio
skmonirEarliest, May '20
EgorKulikovFastest, 0.0s
YouKnowWhoLightest, 918 kB
omar24Shortest, 736B
Toph uses cookies. By continuing you agree to our Cookie Policy.