Dãy số Bitonic.

Một dãy số được gọi là Bi-tonic nếu nó được chia thành hai.Dãy đầu tăng dần và dãy tiếp theo giảm dần. Nhiệm vụ của bạn là tìm tổng lớn nhất dãy con Bi-tonic của dãy số A[]. Ví dụ với dãy A[] = ta có kết quả là 194 tương ứng với dãy Bi-tonic .

Input Format

Dòng đầu tiên đưa vào N là số phần tử của dãy A[]; Dòng tiếp theo đưa vào N số A[i]; các số được viết cách nhau một vài khoảng trống.(1<=N<=100; 1<=A[i]<=100)

Constraints

.

Output Format

In ra kết quả của bài toán

Ví dụ:

Dữ liệu vào

7
1 2 3 98 120 4 100

Dữ liệu ra

324