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

Poveste si cerinta...

Andreea si Ioana au $N$ turnuri de diferite inaltimi. Ele aseaza turnurile pe masa, in linie dreapta si numeroteaza turnurile de la $1$ la $N$ de la cel mai din stanga la cel mai din dreapta. Cele doua fete plasează apoi in fiecare turn cate un soldatel de jucarie. Soldatelul din turnul $i$ poate vedea orice turn $j$ aflat in stanga sa $(j < i)$ daca intre cele doua turnuri nu exista un turn $k$ $(j < k < i)$ astfel incat turnul $k$ are o inaltime strict mai mare decat turnul $i$. Definim vizibilitatea totala a soldateilor ca fiind suma numarului de turnuri pe care le vede fiecare soldatel. Pentru fiecare turn $i$ $(1&le;i&le;N)$ cele doua fete se intreaba care ar fi vizibilitatea totala a soldateilor daca ar elimina de pe masa turnul $i$. Determinati suma vizibilitatilor totale ale soldateilor ce se obtin eliminand pe rand fiecare dintre cele $N$ turnuri.

h2. Date de intrare

Fisierul de intrare $turnuri.in$ ...

Prima linie a fisierului de intrare $turnuri.in$ va contine numarul natural $N$, reprezentand numarul de turnuri. Urmeaza $N$ linii, pe linia $i+1$ aflandu-se inaltimea turnului $i$.

h2. Date de iesire

In fisierul de iesire $turnuri.out$ ...

Fisierul de iesire $turnuri.out$ va contine o singura linie pe care va fi scrisa suma vizibilitatilor totale ale soldateilor, vizibilitati totale ce se obtin eliminand pe rand fiecare dintre cele $N$ turnuri.

h2. Restrictii

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

* $1 ≤ N ≤ 1 000 000$
* Inaltimile turnurilor sunt numere naturale din intervalul $[1,2 000 000 000]$ si sunt distincte doua cate doua

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

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

|4
 7
 10
 2
 5
|10

|
h3. Explicatie

...

Daca eliminam turnul $1$ se obtine sirul de turnuri $10, 2, 5$. Vizibilitatea soldatelului din turnul cu inaltimea $2$ este $1$, iar vizibilitatea celui din turnul cu intaltimea $5$ este $2$. Suma vibilitatilor totale obtinute prin eliminarea turnului $1$, $2$, $3$, respectiv $4$ este $3+3+2+2=10$.

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