Cho dãy số gồm \(N\) \((3 \le N \le 10^5)\) số nguyên \(A_1, A_2, ... A_n\) \((0 \lt A_i \le 10^5)\)

Với bộ ba số \((i,j,k)\) trong đó \(1 \le i \lt j \lt k \le n\) hãy tìm giá trị \(S = 3A_i + 2A_j - 5A_k\) sao cho \(S\) đạt giá trị lớn nhất

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(N\)
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2,...A_n\) giữa các số cách nhau một khoảng trắng

Dữ liệu ra

Giá trị \(S\) lớn nhất.

Scoring

• Subtask 1 (20% số điểm): \(N \le 100\)
• Subtask 2 (40% số điểm): \(N \le 5 \times 10^3\)
• Subtask 3 (40% số điểm): \(N \le 10^5\)

Input 1

10
4 9 7 9 4 3 2 9 15 6

Output 1

35