XrkArul With Elden Ring (Hard Version)

The only difference with the easy version is that when XrkArul reaches one(left or right) end of the line , he can continue in the same direction from the other end of the line until he reaches the boss he  initially choose.（That means you can consider the world a ring ,not a line）

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 ai 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 ai exp . Note that once he chooses a direction to move,when XrkArul reaches one(left or right) end of the line , he can continue in the same direction from the other end of the line until he reaches the boss he  initially choose.

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.

5
1 2 8 2 3

10

Note: In this case,XrkArul can start at position 3 and choose to move right,this way the exp he can get is 8+1+1+0+0=10.