Infinite Sequence

Time limit2sMemory limit1024 MB

Summary

Given array A, repeat it forever and subtract each index i from the i-th value. Find the largest sum of a contiguous segment.

Level: Medium7 of 10
Topics: Prefix sum, Math, Dynamic programming
Solved: No attempts yet

Problem

Sehun received a sequence $A$ of $N$ integers as a birthday gift. Finding the sequence too short, he decided to build an infinitely long sequence in the following way.

First, concatenate sequence $A$ infinitely many times. Then, for every positive integer $i$ , subtract $i$ from the $i$ -th number.

Pleased that the sequence had become longer, Sehun decided to pick several consecutive numbers from the resulting sequence and add them up. Since he likes large values, he wants to make this sum as large as possible.

For example, if $A$ is $[9, 1, 7]$ , the new sequence becomes $[8, -1, 4, 5, -4, 1, \ldots]$ , and its maximum contiguous sum is the sum of the 1st through 4th numbers, $8-1+4+5=16$ .

Input

The first line contains $N$ , the length of sequence $A$ . ( $1 \le N \le 500\,000$ )

The second line contains the elements $A_1, A_2, \ldots, A_N$ , separated by spaces. ( $|A_i| < 2^{31}$ )

Output

Print the answer to the problem.

Hint

Since the input is large, use fast input and output as described in the language guide on pages 2-4 of the problem booklet.

Examples2

Example 1
Input
```
3
9 1 7
```
Expected output
```
16
```
Example 2
Input
```
2
-12 -17
```
Expected output
```
0
```