| 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
| turnuri.in | turnuri.out |
|---|---|
| 4 7 10 2 5 | 10 |
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.
