P10957 Circular Transport

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.

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

Output one integer, the maximum cost.

Constraints: $2 \le N \le 10^6$, $1 \le A_i \le 10^7$. Translated by ChatGPT 5