Cho dãy số nguyên ~a_1, a_2, \dots, a_N~. Dãy số ~a_{i_1}, a_{i_2}, \dots, a_{i_k}~ được gọi là dãy con của dãy đã cho nếu ~1 \le i_1 < i_2 < \dots < i_k \le N~.

Một dãy số ~b_1, b_2, \dots, b_m~ được gọi là dãy hình nón nếu tồn tại vị trí ~j~ sao cho:

~b_1 < b_2 < \dots < b_j > b_{j+1} > \dots > b_m~ (với ~1 < j < m~).

Yêu cầu: Tìm dãy con hình nón có tổng lớn nhất.

Input

• Dòng thứ nhất chứa số nguyên ~N~ ~(3 \le N \le 1000)~;

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

Các số trên cùng dòng cách nhau ít nhất một dấu cách.

Output

Một số nguyên duy nhất là kết quả tìm được. Trường hợp không tồn tại dãy con hình nón thì ghi ~0~.

Scoring

Sample Input 1

8
2 1 1 9 2 1 2 5

Sample Output 1

16

Sample Input 2

6
7 5 3 1 2 3

Sample Output 2

0

Notes

Trong ví dụ thứ nhất, dãy con hình nón có tổng lớn nhất là ~2, 9, 5~.

Trong ví dụ thứ hai, không tồn tại dãy con hình nón.