XrkArul With Elden Ring (Easy Version)

XrkArul is getting addicted to the game called Elden Ring,in which the world is on a line .There are n bosses on this line ,which XrkArul can get a_i exp if he beat the i th boss.

Now XrkArul can choose a boss among n bosses , and select a direction he moves (left or right) , in every second he will beat a boss.When XrkArul is on position i , he will beat the i th boss and get a_i exp . Note that once he chooses a direction, he can only move to the end in one direction and can not turn back until he reaches one (left or right) end of the line. 

For every second, the other boss which are not beated will lose their exp by 1 (minimum to 0). Because XrkArul is a skilled gamer, he can always get the most exp in the end. 

Can you calculate the exp that XrkArul eventually gets? 

Note that once a boss is beated, he will no longer exist.

The first line contains only integer n (1≤ n ≤1e6).

The second line contains n integers a1,a2,...,an  (0≤ ai ≤1e9).

An integer , the exp that XrkArul eventually gets.

4
1 5 3 2

7

Note:In this case,XrkArul can start at position 2 and choose to move right,this way the exp he can get is 5+2+0=7.