Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Hizitizi's Array Cutting

By Riaz_BSMRSTU · 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

    A = a1 + … + ai.
    B = ai+1 + … + aj.
    C = aj+1 + … + an.

    Then, (A - B)2 + (B - C)2 is minimum.

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

Discussion

Statistics


60% Solution Ratio

skmonirEarliest, 1M ago

EgorKulikovFastest, 0.0s

YouKnowWhoLightest, 918 kB

omar24Shortest, 736B

Submit

Login to submit