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:
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
The first line of the input contains a single integer N (2 ≤ N ≤ 200000) -- the number of memes.
The second line contains N integers Ai (0 ≤ Ai ≤ 1000000) -- the number of upvotes of meme #i.
Print a single integer -- the maximum possible NASDANQ index that Jiefeng the Meme Magician can achieve.
Subtask 1 (12%): 2 ≤ N ≤ 1000.
Subtask 2 (88%): No additional constraints.
Subtask 3 (0%): Sample testcases.
4 4 3 2 5
5 1 1 2 7 1
3 1 1 2
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.