mememagic

Meme Magic

O'Shaliday the Green One, God of Chaos, Bringer of Light, granter of meme magic, send your blessings down upon us! Meme magic elected the US President, helped anon get a girlfriend, exposed Comet Pizza, rekt'd the lives of SJWs and libtards, and provided a constant resupply of Good Boy Points for tendies. Such a great power can only be harnessed from a lifetime of devoted shitposting, praising Kek and rolling dubs, an accomplishment held only by one man -- Jiefeng the Meme Magician, the newly appointed Secretariat-General Premier of /pol/.

To understand this power, it is imperative to understand the following:

1. There are N memes in existence at any one time, numbered from 1 to N in order of the time of their first appearance (no cancer that is REEEEEEposts).
2. Memes become stale over time as it passes from the threshold of 4chan->Reddit->9gag->iFunny->Facebook->Instagram. As such, memes have a corresponding dankness value of 1 to N where 1 is an overused normie 9gag meme with a half life of 5 years and N is the freshest dank meme.
3. The array A_i shows the accumulated upvotes that meme #i has received (memes cannot be downvoted to negative upvotes).
4. The NASDANQ index, which tracks the overall health of the meme economy, is computed by the formula sum(A_i * i).

The power that Jiefeng has been entrusted with allows him to alter the course of meme history. Specifically, he can pick a single meme and move it to any point in history, hence changing the numbering of the memes between. In particular, he is able to move the meme to the beginning or to the end of meme history, or even back to the same position.

Jiefeng is only able to summon his power exactly once. As a loyal shitposter striving to praise and glorify Kek, he would like to use his power in such a way that maximises NASDANQ index.

And don't forget to PRAISE KEK!

-- Another quality shitpost by Fanpu

Input

The first line of the input contains a single integer N (2 ≤ N ≤ 200000) -- the number of memes.

The second line contains N integers A_i (0 ≤ A_i ≤ 1000000) -- the number of upvotes of meme #i.

Output

Print a single integer -- the maximum possible NASDANQ index that Jiefeng the Meme Magician can achieve.

Subtasks

Subtask 1 (12%): 2 ≤ N ≤ 1000.
Subtask 2 (88%): No additional constraints.
Subtask 3 (0%): Sample testcases.

Sample Input 1

4
4 3 2 5

Sample Output 1

39

Sample Input 2

5
1 1 2 7 1

Sample Output 2

49

Sample Input 3

3
1 1 2

Sample Output 3

9

Explanation

In the first sample, Jiefeng could pick the first meme and place it before the last (before the meme with 5 upvotes). This will bring the index up to 3*1 + 2*2 + 4*3 + 5*4 = 39.

In the second sample, Jiefeng could pick the last meme and place it before the third. This will bring the index up to 1*1 + 1*2 + 1*3 + 2*4 + 7*5 = 49.