== include(page="template/taskheader" task_id="blackwater") ==

Poveste şi cerinţă...

Stannis Baratheon incearcă să cucerească King's Landing. El atacă prin portul oraşului şi dispune de $N$ bărci in şir indian (prima este cea mai apropiată de port, apoi a doua e in spatele primei şi tot aşa). Fiecare barcă are puterea ei de atac specifică, dar aceasta putere scade în funcţie de distanţa bărcii faţă de port.
 
Dacă puterile bărcilor sunt vazute ca un vector de numere întregi, de exemplu $V = [3, 4, 2, 1, 5]$ atunci prima va lovi cu putere $[3/1]$, a doua cu putere $[4/2] = 2$, a treia cu putere $[2/3] = 0$, a patra cu putere $[1/4] = 0$ si a cincea cu putere $[5/5] = 1$, unde $[x]$ este partea întreagă inferioară numărului $x$. Aşadar, suma tuturor loviturilor date de bărci este <tex>\lfloor{$V_{1}/1}\rfloor + \lfloor{V_{2}/2}\rfloor + \lfloor{V_{3}/3}\rfloor + .. + \lfloor{V_{N}/N$}\rfloor </tex>.
 
Stannis începe lupta în curând, dar realizează că poate creşte suma loviturilor reorganizand bărcile, dar el, din cauza că este grabit, poate doar să permute circular vectorul cu bărci, de exemplu $[3, 4, 2, 1, 5]$ permutat circular la stânga de $2$ ori va rezulta în $[2, 1, 5, 3, 4]$. Care este suma maximă a loviturilor daca poti permuta circular la stânga de ori de câte ori vrei (eventual $0$ ori)?

h2. Date de intrare

Fişierul de intrare $blackwater.in$ ...

Fişierul de intrare $blackwater.in$ va contine pe prima linie un numar natural $N$.
A doua linie va contine cele n numere intregi ce formeaza vectorul $V$.

h2. Date de ieşire

În fişierul de ieşire $blackwater.out$ ...

În fişierul de ieşire $blackwater.out$ se va afisa pe prima linie un singur numar natural, suma maxima a puterilor barcilor dupa permutari.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ n ≤ 80 000$
* $0 ≤ v[i] ≤ 100 000$
* Pentru $11$ puncte se asigura ca $1 ≤ n ≤ 5000$
* Pentru $10$ puncte se asigura ca $1 ≤ k ≤ 5000 unde k este numarul de elemente nenule$
* Pentru alte $16$ puncte se asigura ca valorile elementelor vor fi doar $0$ sau $100 000$

h2. Exemplu
table(example). |_. blackwater.in |_. blackwater.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5
3 4 2 1 5
|7
|
| 3
100000 0 100000
|150000

|
h3. Explicaţie

...

$[3, 4, 2, 1, 5]$ permutat la stanga de $4$ ori va rezulta $[5, 3, 4, 2, 1]$ -> $[5/1] + [3/2] + [4/3] + [2/4] + [1/5] = 5 + 1 + 1 + 0 + 0 = 7$
$[100000, 0, 100000]$ permutat la stanga de $2$ ori va rezulta $[100000, 100000, 0]$ -> $[100000/1] + [100000/2] + [0/3] = 100000 + 50000 + 0 = 150000$

== include(page="template/taskfooter" task_id="blackwater") ==