Juice

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Three teams from Lviv University advanced to the world programming semifinals. On this occasion, the team coaches purchased \(n\) bottles of juice and arranged them in a single row, with the \(i\)-th bottle containing \(a_i\) grams of juice.

Faced with the main coach is the task to divide the bottles into three contiguous segments so that each team gets at least one bottle, and each bottle belongs to exactly one team. Moreover, to ensure that the teams are in equal conditions at the competition, the difference between the maximum and minimum amount of juice consumed among all teams should be the minimum possible.

Since the coach has already tasted birch juice, he instructed you to solve this problem.

Input

The first line contains an integer \(n\) — the number of bottles of juice.

The next line contains \(n\) numbers \(a_i\) — the capacity of the \(i\)-th bottle in grams.

Output

In a single line, output an integer — the minimum possible difference between the maximum and minimum amounts of consumed juice in grams.

Constraints

In 10 tests:

\(3 \le n \le 2\cdot10^3\),

\(1 \le a_i \le 10^6\),

in all remaining tests:

\(3 \le n \le 10^5\),

\(1 \le a_i \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7 1 3 2 4 1 3 7	2

Notes

In the example, it is optimal to divide the bottles into segments [1, 3, 2], [4, 1, 3], [7]. Then the first team will drink a total of 6 grams of juice, the second — 8, the third — 7. The difference between the maximum and minimum values is \(8 - 6 = 2\).