Cho \(n\) số nguyên \(a_1, a_2, ... a_n\), tìm 3 chỉ số \(i, j, k\) \((1 \le i \lt j \lt k \le n)\) thỏa mãn \(S = a_i - a_j + a_k\) lớn nhất.

Đầu vào

Dòng đầu tiên là số nguyên dương \(n\) \((3 \le n \le 10^5)\)

Dòng thứ 2 là dãy số nguyên \(a\) \((|a_i| \le 10^9)\)

Đầu ra

Một số nguyên duy nhất là \(S\) lớn nhất tìm được

Ví dụ

Đầu vào

7
1 2 -4 3 7 -5 6

Đầu ra

18