Bộ ba

Cho dãy gồm \(N\) số nguyên \(A_1, A_2, \ldots, A_N\) \((1 \le N \le 10^6,\ 0 < A_i \le 10^5)\).

Với bộ ba chỉ số \((i, j, k)\) thỏa mãn \(1 \le i < j < k \le N\), hãy tính giá trị:
$
S = 3A_i + 2A_j - 5A_k
$
và tìm bộ ba sao cho \(S\) đạt giá trị lớn nhất có thể.

Input

• Dòng đầu tiên chứa số nguyên \(N\) \((1 \le N \le 10^6)\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \ldots, A_N\) cách nhau bởi dấu cách.

Output

In ra một dòng duy nhất là giá trị lớn nhất của \(S\) tìm được.

Scoring

• Subtask 1 (30%): \(N \le 100\)
• Subtask 2 (30%): \(N \le 5000\)
• Subtask 3 (40%): \(N \le 10^6\)

Sample Input 1

10
4 9 7 9 4 3 2 9 15 6

Sample Output 1

35

Sample Input 2

3
1 1 10

Sample Output 2

-45

Notes

Chọn \(i=2, j=4, k=7\) tương ứng với \(A_i = 9,\ A_j = 9,\ A_k = 2\), ta được:
$
S = 3 \cdot 9 + 2 \cdot 9 - 5 \cdot 2 = 27 + 18 - 10 = 35
$