turnuri

Andreea şi Ioana au $N$ turnuri de diferite înălţimi. Ele aşează turnurile pe masă, în linie dreaptă şi numerotează turnurile de la $1$ la $N$ de la cel mai din stânga la cel mai din dreapta. Cele două fete plasează apoi în fiecare turn câte un soldăţel de jucărie. Soldăţelul din turnul $i$ poate vedea orice turn $j$ aflat în stânga sa $(j < i)$ dacă între cele două turnuri nu există un turn $k (j < k < i)$ astfel încât turnul $k$ are o înălţime strict mai mare decât turnul $i$.

Definim vizibilitatea totală a soldăţeilor ca fiind suma numărului de turnuri pe care le vede fiecare soldăţel. Pentru fiecare turn $i (1 \leq i \leq N)$ cele două fete se întreabă care ar fi vizibilitatea totală a soldăţeilor dacă ar elimina de pe masă turnul $i$.

Cerinţă

Determinaţi suma vizibilităţilor totale ale soldăţeilor ce se obţin eliminând pe rând fiecare dintre cele $N$ turnuri.

Date de intrare

Prima linie a fişierului de intrare turnuri.in va conţine numărul natural $N$, reprezentând numărul de turnuri. Urmează $N$ linii, pe linia $i+1$ aflându-se înălţimea turnului $i$.

Date de ieșire

Fişierul de ieşire turnuri.out va conţine o singură linie pe care va fi scrisă suma vizibilităţilor totale ale soldăţeilor, vizibilităţi totale ce se obţin eliminând pe rând fiecare dintre cele $N$ turnuri.

Restricții și precizări

• $2 \leq N \leq 1 \ 000 \ 000$;
• Înălţimile turnurilor sunt numere naturale din intervalul $[1,2 \cdot 10^9]$ şi sunt distincte două câte două.

Exemplu

turnuri.in

4
7
10
2
5

turnuri.out

10

Explicație

Pe masă sunt $4$ turnuri, având în ordinea de la stânga la dreapta înălţimile $7$, $10$, $2$, şi respectiv $5$. Dacă eliminăm turnul $1$ se obţine şirul de turnuri $10, 2, 5$.

Vizibilitatea totală e $3$.

Dacă eliminăm turnul $2$ se obţine şirul de turnuri $7, 2, 5$:

Vizibilitatea totală e $3$.

Dacă eliminăm turnul $2$ se obţine şirul de turnuri $7, 10, 5$:

Vizibilitatea totală e $2$.

Dacă eliminăm turnul $2$ se obţine şirul de turnuri $7, 10, 2$:

Vizibilitatea totală e $2$.