Fluortanten

문제

Björn och $n-1n-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 $11$ till $nn$, och person $ii$ står på plats $ii$ i kön. Person $ii$ har också ett värde $a_{i}a\_i$, som visar hur ogärna personen vill träffa fluortanten. Person $ii$:s glädje över sin plats i kön är $i\cdot a_{i}i\; \backslash cdot\; a\_i$. Vissa personer kan ha negativ $a_{i}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=0a\_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}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.

입력

Den första raden innehåller ett heltal $nn$, antalet personer i kön. På nästa rad följer $nn$ heltal, där det $ii$:te talet är $a_{i}a\_i$. $1\le n\le {10}^{6}1\; \backslash leq\; n\; \backslash leq\; 10^6$, $-1000\le a_i\le 1000-1000\; \backslash leq\; a\_i\; \backslash leq\; 1000$.

출력

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