Đề bài

Cho dãy số ~a(n)~ gồm các số nguyên ~a_1, a_2, \dots, a_n~. Hãy tìm bộ ba số ~a_i, a_j, a_k~ sao cho ~T = a_i + 2a_j + 3a_k~ đạt giá trị lớn nhất, với ~1 \leq i < j < k \leq n~.

Ví dụ: với dãy ~a(5)~: 2, 2, 10, 4, 5 thì ~T = 2 + 2 \times 10 + 3 \times 5 = 37~ là lớn nhất.

Input

Dữ liệu vào từ tệp văn bản bobaso.inp gồm:

• Dòng 1 chứa một số nguyên ~n~.
• Dòng thứ hai là dãy ~a_1, a_2, \dots, a_n~ mỗi số cách nhau một khoảng trắng.

Output

Kết quả ghi vào tệp văn bản bobaso.out: Giá trị lớn nhất ~T~ tìm được.

Ví dụ

Sample Input

5
2 2 10 4 5

Sample Output

37

Giới hạn

• ~3 \leq n \leq 10^6~
• ~0 \leq a_i \leq 10^6~
• 80% số test ứng với 80% số điểm của bài toán có: ~3 \leq n \leq 10^2~.
• 20% số test ứng với 20% số điểm của bài toán có: ~10^2 < n \leq 10^6~.