Cho dãy số gồm ~n~ số nguyên ~a_1, a_2, …, a_n~. Tìm giá trị lớn nhất của hàm ~f(i, j, k) = a_i + 2a_j + 3a_k~ với ~1 \leq i < j < k \leq n~.

Ví dụ: với dãy gồm 5 số -1, 2, -2, -3, 5 thì ~f(1, 2, 5)= -1 + 2×2 + 3×5 = 18~ là lớn nhất.

Input

• Dòng thứ nhất là số nguyên ~n~ ~(3 \leq n \leq 10^5)~.

• Dòng thứ hai là ~n~ số nguyên ~a_1, a_2, …, a_n~ mỗi số cách nhau một khoảng trắng ~(|a_i| \leq 10^9)~

Output

• Là giá trị lớn nhất của hàm ~f(i, j, k)~ tìm được.

Sample Input

5
-1 2 -2 -3 5

Sample Output

18

Note

• Bài này quy hoạch động, một hướng dẫn nhỏ cho các bạn