Cho dãy số nguyên \(a_1,a_2,...,a_n\).

Tìm hai chỉ số \(i,j\) thỏa mãn:

• \(i < j\)
• \(|a_i + a_j|\) đạt giá trị lớn nhất

Input

• Dòng đầu ghi số nguyên dương \(n\) \((n \le 200 000)\)
• Dòng sau ghi \(n\) số nguyên \(a_1,a_2,...,a_n\) \((-10^9 \le a_i \le 10^9)\)

Output

• \(\max(|a_i+a_j|)\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 2000\)
• Subtask \(2\) (\(70\%\) số điểm): \(n \le 200 000\)

Example

3
1 2 3

5