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