Cho trước một số tự nhiên \(N\) (\(3 \le N \le 10^6\)) và dãy gồm \(N\) số nguyên \(a_1, a_2, \dots, a_N\). Giá trị tuyệt đối của các số nguyên trong dãy không vượt quá \(32000\).

Yêu cầu

Tìm bộ ba số \(a, b, c\) tại các vị trí đôi một khác nhau trong dãy số trên sao cho giá trị tuyệt đối tổng của chúng là lớn nhất. Nói cách khác, \(|a + b + c|\) đạt giá trị lớn nhất. Biết rằng trong dãy đã cho luôn tồn tại ít nhất một bộ ba số.

Input

Đọc từ bàn phím theo cấu trúc sau:

• Dòng đầu tiên là một số tự nhiên \(N\) duy nhất.
• \(N\) dòng tiếp theo, mỗi dòng chứa một số nguyên của dãy số đã cho.

Output

• Xuất ra một số nguyên duy nhất là giá trị \(|a + b + c|\) lớn nhất tìm được.

Example

4
3
-2
6
5

14

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(3 \le N \le 450\).
• Subtask \(2\) (\(30\%\) số điểm): \(450 < N \le 10^4\).
• Subtask \(3\) (\(30\%\) số điểm): \(10^4 < N \le 10^6\).