Cho dãy số nguyên gồm \(n\) phần tử \(a_1,a_2,…,a_n\).

Yêu Cầu: Tìm bộ ba chỉ số \(i < j < k\) sao cho \(a_i - a_j + a_k\) là lớn nhất

Dữ liệu:

• Dòng đầu tiên chứa số \(n (3≤n ≤10^5)\).
• Dòng tiếp theo chưa \(n\) số nguyên \(a_1,a_2,…,a_n (-10^9≤a_i≤10^9)\).

Kết quả: Ghi ra một số nguyên duy nhất là giá trị lớn nhất của bài toán.

Input:

5
1 2 3 4 5

Output:

4

Subtask:

• 50% số test ứng với 50 số điểm bài toán có \(N \le 100\)
• 50% số test còn lại ứng với 50 số điểm còn lại có \(N \le 10^5\)