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 books, where the -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 + \dots + S_{|S|} - |S| + 1, where is the size of the set .
Find the maximum interestingness rating over all subsegments [l;r] (1 \le l \le r \le n) of the array .
The first line contains an integer (1 \le n \le 10^6) — the number of books.
The second line contains integers a_i (-10^9 \le a_i \le 10^9) — the interestingness ratings of the books.
Output a single integer — the answer to the problem.
Example 1
Example 2
Example 3
Solutions that work correctly for n \le 2000 will receive at least points.
Solutions that work correctly for a_i \le a_{i+1} for all i < n will receive at least points.