### ** 4cuts**

### Title

### Problem Statement

Snuke has an integer sequence `A` of length `N`.

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.
Snuke 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

`4 ≤ N ≤ 2 × 10`^{5}
`1 ≤ A`_{i} ≤ 10^{9}
- All values in input are integers.

### Input

Input is given from Standard Input in the following format:

`N`
`A`_{1} `A`_{2} `...` `A`_{N}

### Output

Find the minimum possible absolute difference of the maximum and the minimum among `P,Q,R,S`.

### Sample Input 1

5
3 2 4 1 2

### Sample Output 1

2

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 Input 2

10
10 71 84 33 6 47 23 25 52 64

### Sample Output 2

36

### Sample Input 3

7
1 2 3 1000000000 4 5 6

### Sample Output 3

999999994