Fişierul intrare/ieşire:	turnuri.in, turnuri.out	Sursă	Lot 2008 - Piatra Neamt, Baraj3
Autor	Adrian Airinei	Adăugată de	Airinei Adrian •astronomy
Timp execuţie pe test	0.225 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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.

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.

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.

Restrictii

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

Exemplu

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 vizibilitatilor totale obtinute prin eliminarea turnului 1, 2, 3, respectiv 4 este 3+3+2+2=10.

Cum se trimit solutii?