I got this question today In an qualifying round for a company SDE role. I wasn't able to solve the problem. Honestly, I would love if you could share some insight into the solution.

Initially I thought this is a dp problem, but could not come up with solution that can pass even a single test case.

Problem Statement

Bob loves to play with arrays. Since he is a kid, he likes to cut the arrays into smaller sequences.

One day his mom got him an integer sequence A of length N. Since he is a super talented guy, he has some special requirements.

He will make three cuts in A and divide it into four (non-empty) contiguous subsequences B, C, D and E. The positions of the cuts can be freely chosen.

Let P, Q, R, S be the sums of the elements in B, C, D, E, respectively. Bob is happier when the absolute difference of the maximum and the minimum among P, Q, R, S is smaller. Find the minimum possible absolute difference of the maximum and the minimum among P, Q, R, S.

Constraints

1 <= N <= 100000 1 <= Ai <= 1000000000

Input Format

The first line will contain the integer n, that is the number of integers in the array. The second line contains the array elements.

Output Format

Print the minimum absolute difference of the maximum and the minimum among P,Q,R,S.

Sample Testcase #0

Testcase Input
5
3 2 4 1 2
Testcase Output
2
Explanation
If we divide A as B,C,D,E=(3),(2),(4),(1,2), then P=3,Q=2,R=4,S=1+2=3. Here, the maximum and the minimum among P, Q, R, S are 4 and 2, with the absolute difference of 2. We cannot make the absolute difference of the maximum and the minimum less than 2, so the answer is 2.

Sample Testcase #1
Testcase Input
5
46 13 7 2 31
Testcase Output
37