Một robot địa hình đang thực hiện nhiệm vụ khảo sát ~n~ trạm, các trạm được đánh số từ ~1~ đến ~n~. Trạm thứ ~i~ có độ cao là ~a_i~. Một danh sách khảo sát gồm ~k~ trạm ~x_1, x_2, \dots, x_k~ (~1 \le x_1 < x_2 < \dots < x_k \le n~) được gọi là đường đi phù hợp nếu thỏa mãn một trong các điều kiện sau:

1. Chỉ khảo sát duy nhất một trạm (~k=1~).

2. Độ cao của các trạm theo thứ tự là dãy tăng dần hoặc dãy giảm dần.

3. Tồn tại chỉ số ~p~ (~1 < p < k~) sao cho ~a[x_1] < a[x_2] < \dots < a[x_{p-1}] < a[x_p] > a[x_{p+1}] > \dots > a[x_k]~, với ~k \ge 3~.

Khi đến khảo sát tại trạm ~i~, robot được nạp thêm số năng lượng đúng bằng tổng các chữ số của ~a_i~. Gọi ~S~ là tổng mức năng lượng robot nhận được từ một đường đi phù hợp.

Yêu cầu: Hãy tìm mức năng lượng ~S~ lớn nhất robot có thể nhận được.

Input

• Dòng đầu chứa số nguyên dương ~n~ (~n \le 10^5~).

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~a_i \le 10^9~).

Các số trên cùng dòng được ghi cách nhau một dấu cách.

Output

Một số nguyên duy nhất là kết quả của bài toán.

Scoring

Sample Input 1

9
15 28 28 9 35 29 18 7 2

Sample Output 1

53

Sample Input 2

6
9 11 13 24 24 26

Sample Output 2

29

Notes

Trong ví dụ thứ nhất, chọn dãy trạm ~[15, 28, 35, 29, 18, 7, 2]~ (tăng từ ~15 \rightarrow 35~ rồi giảm dần xuống ~2~). ~S_{\max}=(1+5)+(2+8)+(3+5)+(2+9)+(1+8)+7+2=53~.

Trong ví dụ thứ hai, chọn dãy trạm ~[9, 11, 13, 24, 26]~ (tăng từ ~9 \rightarrow 26~). ~S_{\max}=9+(1+1)+(1+3)+(2+4)+(2+6)=29~.