== include(page="template/taskheader" task_id="turnuri") ==
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 plaseaza 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≤i≤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.
Poveste si cerinta...
h2. Date de intrare
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$.
Fisierul de intrare $turnuri.in$ ...
h2. Date de iesire
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.
In fisierul de iesire $turnuri.out$ ...
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 |
|4
7
10
2
5
|10
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
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") ==
