Problem Description

Along a circular road, there are $N$ warehouses evenly spaced, numbered from $1$ to $N$. The distance between warehouse $i$ and warehouse $j$ is defined as $dist(i,j)=\min(|i-j|,N-|i-j|)$, that is, the shorter one of the counterclockwise or clockwise distance from $i$ to $j$.

Each warehouse stores some goods. The inventory of warehouse $i$ is $A_i$.

The cost to transport goods between warehouses $i$ and $j$ is $A_i+A_j+dist(i,j)$.

Find between which two warehouses the transport cost is the maximum.

Input Format

The first line contains an integer $N$.

The second line contains $N$ integers $A_1 \sim A_N$.

Output Format

Output one integer, the maximum cost.

5
1 8 6 2 5

15

Hint

Constraints: $2 \le N \le 10^6$, $1 \le A_i \le 10^7$.

Translated by ChatGPT 5