# Practice on Toph

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

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

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.

- Every part is non-empty.
- If we take two index
**i**and**j**(**j**>**i**), andA = a

_{1}+ … + a_{i}.

B = a_{i+1}+ … + a_{j}.

C = a_{j+1}+ … + a_{n}.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 will contain **T** (1 ≤ **T** ≤ 100) test cases.

Each case will contain two lines of input. First line will contain **n** (3 ≤ **n** ≤ 10^{5}), length of the array.

Next line will contain **n** integer (a_{1}, a_{2} … a_{n}), where (1 ≤ a_{i} ≤ 10^{4}).

Note: Sum of **n** over all test cases won’t be more than 10^{6.}

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

Input | Output |
---|---|

1 5 1 2 3 1 2 | 0 |

60% Solution Ratio

skmonirEarliest,

EgorKulikovFastest, 0.0s

YouKnowWhoLightest, 918 kB

omar24Shortest, 736B

Login to submit