#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

### 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:

NA_{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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 37 | 1s | 256MB | Average |

2 | 0 | 3 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o 4cuts -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512