Maximum Transportation Cost on a Circular Road

We are given ( N ) warehouses evenly distributed along a circular road, numbered from ( 1 ) to ( N ). The distance between warehouse ( i ) and warehouse ( j ) is defined as

[ \text{dist}(i,j) = \min(|i-j|, N-|i-j|) ]

Each warehouse ( i ) stores ( A_i ) goods. The cost to transport goods between warehouse ( i ) and ( j ) is defined as

[ \text{cost}(i,j) = A_i + A_j + \text{dist}(i,j) ]

Your task is to find the maximum transportation cost among all pairs of warehouses.

inputFormat

The first line contains a single integer ( N ) (the number of warehouses). The second line contains ( N ) integers ( A_1, A_2, \ldots, A_N ) representing the inventory of each warehouse.

outputFormat

Output a single integer representing the maximum transportation cost.

sample

5
1 2 4 5 1

11