Rezolvare PBinfo #3659

Pentru că e criză, cu ocazia campaniei electorale, în loc de găleți pline cu făină, zahăr și bilete la teatru primiți un șir a1, a2, …, an care reprezintă o permutare a mulțimii {1,2,...,n}. Pentru fiecare secvență nevidă a permutării costul ei este valoarea maximă din acea secvență. De exemplu, costul secvenței 4,2,6,1,3,5 este 6, iar costul secvenței 4,2 este 4.

Cerința

Să se calculeze suma totală a costurilor tuturor secvențelor.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi șirul de n numere naturale, separate prin spații.

Date de ieșire

Programul va afișa pe ecran numărul S, reprezentând suma costurilor tuturor secvențelor.

Restricții și precizări

• 2 ≤ n ≤ 100.000
• șirul de numere este o permutare a mulțimii {1,2,...,n}

Exemplu:

Intrare

4
2 3 4 1

Ieșire

33

Explicație

Secvențele nevide ale permutării 2,3,4,1 sunt:
2 – cost 2
2 3 – cost 3
2 3 4 – cost 4
2 3 4 1 – cost 4
3 – cost 3
3 4 – cost 4
3 4 1 – cost 4
4 – cost 4
4 1 – cost 4
1 – cost 1
Costul total este 2+3+4+4+3+4+4+4+4+1=33.