Chia kẹo

Bạn có \(N\) gói kẹo, được đánh số từ \(1\) đến \(N\). Gói kẹo thứ \(i\) chứa \(A_i\) chiếc kẹo.

Hãy chia các gói kẹo thành \(3\) phần liên tiếp (mỗi phần có ít nhất một gói) như sau:

• Phần 1: Gồm các gói từ \(1\) đến \(i\), có tổng số kẹo là \(x = A_1 + \dots + A_i\)

• Phần 2: Gồm các gói từ \(i+1\) đến \(j\), có tổng số kẹo là \(y = A_{i+1} + \dots + A_j\)

• Phần 3: Gồm các gói từ \(j+1\) đến \(N\), có tổng số kẹo là \(z = A_{j+1} + \dots + A_N\)

Với \(1 \le i < j < N\). Nhiệm vụ của bạn là chọn cách chia \((i, j)\) sao cho hiệu giữa phần nhiều kẹo nhất và ít kẹo nhất là nhỏ nhất, tức là giá trị:

là nhỏ nhất có thể.

Input

Dòng đầu tiên chứa số nguyên \(N\) (\(4 \le N \le 2 \cdot 10^5\)).

Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) (\(1 \le A_i < 10^9\)).

Output

In ra một số nguyên duy nhất --- giá trị nhỏ nhất của \(T\) có thể đạt được.

Scoring

• Subtask 1 (25%): \(4 \le N \le 200\)

• Subtask 2 (35%): \(200 < N \le 2000\)

• Subtask 3 (40%): \(2000 < N \le 2 \cdot 10^5\)