E. The Food Route
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

While Tarija has the famous wine route, in Cochabamba Mateo, Ale, Harrison and Thiago, four friends from UMSS, decided to create something much more urgent: The Food Route.

They have a list of $$$n$$$ food stops in a fixed order (the route cannot be changed). At each stop $$$i$$$, an amount $$$a_i$$$ of food is eaten.

To survive the route, they decide to split it into $$$4$$$ consecutive segments, one for each friend. Each segment must be non-empty, must respect the original order and, together, the four segments must cover the whole route.

The "load" of a person is the sum of the food in their segment. For each segment the sum of its elements is computed, obtaining $$$S_1, S_2, S_3$$$ and $$$S_4$$$. Since nobody wants to end up sleeping in a flowerbed on América Avenue, they want to split the route as fairly as possible.

The goal is to choose the split that minimizes $$$\max(S_1, S_2, S_3, S_4) - \min(S_1, S_2, S_3, S_4)$$$.

Print the minimum possible value of that difference.

Input

The first line contains an integer $$$n$$$ ($$$4 \le n \le 10^5$$$), the number of food stops.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$), where each number is the amount of food eaten at that stop.

Output

Print a single integer: the minimum possible difference between the largest and the smallest sum when splitting the array into 4 non-empty contiguous subarrays.

Examples
Input
6
1 3 2 4 6 5
Output
2
Input
10
28 21 54 10 5 19 2 30 40 1
Output
23
Input
9
23 10 31 55 70 21 10 34 45
Output
36