Tèo và Tí đang chơi một trò chơi với các lá bài. Có \(n\) lá bài được xếp theo thứ tự từ trái qua phải, lá bài thứ \(i\) (\(1 \leq i \leq n\)) có giá trị \(a_i\).

Đầu tiên, Tèo chọn một đoạn con gồm các lá bài từ vị trí \(l\) đến vị trí \(r\) \((1 \leq l \leq r \leq n)\). Sau đó, Tí loại bỏ một lá bài \(j\) từ đoạn con \((l \leq j \leq r)\). Điểm số của trò chơi là tổng giá trị của các lá bài còn lại trong đoạn con. Trong trường hợp Tèo chọn một đoạn con chỉ có một phần tử thì điểm số sau khi Tí loại bỏ một lá bài là \(0\).

Tèo muốn làm điểm số lớn nhất có thể còn Tí sẽ chọn lá bài để điểm số nhỏ nhất có thể. Tèo nên chọn đoạn con nào?

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 10^{5})\) là số lượng lá bài.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((|a_{i}| \leq 10^{9})\) là giá trị trên mỗi lá bài.

Output

• In ra một số nguyên duy nhất là điểm số của trò chơi.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 10^{2}\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 10^{3}\).
• Subtask \(3\) (\(30\%\) số điểm): \(|a_{i}| \leq 10^{2}\).
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
5 -2 10 -1 4

6

3
-7 6 -9

0