What books can lead to...

The author of the daily tasks sits in the library every day, which has a bad effect on his mental state. As you can see, all the tasks in this contest are about books, what will be next...

You have $n$ books, where the $i$-th book has an interestingness rating of $a_i$. You want to read some of them to get the maximum satisfaction, i.e., so that the interestingness of the read books is maximal. However, the interestingness of read books is not always equal to the sum of their interestingness ratings. Over time, you start getting bored of reading, and each subsequent book will be less interesting than the previous ones. More formally, if you have a set of books, the interestingness of reading them will be equal to $S_1+S_2+S_3+\cdots +S_{|S|}-|S|+1$, where $|S|$ is the size of the set $S$.

Find the maximum interestingness rating over all subsegments $[l;r]$ ($1\le l\le r\le n$) of the array $a$.

Input

The first line contains an integer $n$ ($1\le n\le 10^6$) — the number of books.

The second line contains $n$ integers $a_i$ ($-10^9\le a_i\le 10^9$) — the interestingness ratings of the books.

Output

Output a single integer — the answer to the problem.

Examples

Scoring

Solutions that work correctly for $n\le 2000$ will receive at least $10$ points.

Solutions that work correctly for $a_i\le a_{i+1}$ for all $i<n$ will receive at least $20$ points.