Cho số nguyên dương \(n\) và dãy số nguyên \(a_1,a_2,…,a_n\). Một đoạn con \([i,j]\) gồm các phần tử liên tiếp \(a_i,a_{i+1},…,a_j\). Trọng số của đoạn \([i,j]\) được tính bằng tích của giá trị nhỏ nhất với tổng các phần tử trong đoạn đó.

Yêu cầu: Tìm đoạn con gồm các phần tử liên liếp có trọng số lớn nhất.

Input

• Dòng 1 chứa số nguyên \(n(1≤n≤10^5 ).\)

• Dòng thứ 2 chứa \(n\) số nguyên \(a_1,a_2,…,a_n (1≤a_i≤10^6 ).\)

Output

• Ghi một số là tổng trọng số lớn nhất tìm được.

Ràng buộc

• Subtask 1: 40% test với \(n≤10^2\).

• Subtask 2: 60% test với \(n≤10^5\).

Sample Input

6
3 1 6 4 5 2

Sample Output

60