Problem D
Fluortanten

Björn och $n-1$ andra personer står i kön för att träffa fluortanten. Olika personer tycker att det är olika läskigt att träffa fluortanten. Personerna är numrerade från $1$ till $n$, och person $i$ står på plats $i$ i kön. Person $i$ har också ett värde $a_ i$, som visar hur ogärna personen vill träffa fluortanten. Person $i$:s glädje över sin plats i kön är $i \cdot a_ i$. Vissa personer kan ha negativ $a_ i$, vilket betyder att de egentligen vill träffa fluortanten och sålunda är ledsna över att få vänta.

Björn är den enda personen som är helt likgiltig inför att träffa fluortanten, det vill säga han är den enda personen som har $a_ i = 0$. Dessutom är han väldigt godhjärtad, så han bestämmer sig för att lämna kön och sedan gå in i kön igen på någon plats så att den totala glädjen hos alla i kön blir så stor som möjligt. Skriv ett program som givet värdena $a_ i$ för alla personer räknar ut den maximala summan av glädjen i kön om Björn ställer sig på en optimal plats.

Indata

Den första raden innehåller ett heltal $n$, antalet personer i kön. På nästa rad följer $n$ heltal, där det $i$:te talet är $a_ i$. $1 \leq n \leq 10^6$, $-1\, 000 \leq a_ i \leq 1\, 000$.

Output

Skriv ut en rad med ett heltal: den maximala totala glädjen i kön.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempel 1

Björn ställer sig sist i kön. Summan av glädjen blir då $1 \cdot 1 + 2\cdot (-2) + 3 \cdot 0 = -3$.

Om Björn i stället ställt sig först i kön hade summan av glädje blivit $1 \cdot 0 + 2 \cdot 1 + 3 \cdot (-2) = -4$, och i mitten hade den blivit $1 \cdot 1 + 2 \cdot 0 + 3 \cdot (-2) = -5$. Båda dessa är sämre alternativ.

3
1 0 -2

-3

5
0 -8 1 1 5

24

7
2 -4 5 -3 0 -1 2

7