Cel mai nou proiect imobiliar din capitală este compus din N blocuri-turn, construite unul lângă altul, de-a lungul unui bulevard central și numerotate de la 1 la N. Pentru fiecare turn se cunoaște numărul etajelor din care este compus acesta și se mai știe că nu există două turnuri cu același număr de etaje. Ultimele norme urbanistice definesc coeficientul de frumusețe al turnului cu numărul T ca fiind numărul turnurilor din secvența de turnuri care începe cu turnul S, se termină cu turnul D și are următoarele proprietăți:

• 1 ≤ S ≤ T ≤ D ≤ N
• numărul etajelor fiecărui turn din secvență, cu excepţia turnului T, este mai mic decât numărul de etaje ale turnului T;
• Dacă S ≠ 1 atunci turnul S-1 este cel mai apropiat turn din stânga turnului T, care are un număr de etaje strict mai mare decât turnul T;
• Dacă D ≠ N atunci turnul D+1 este cel mai apropiat turn din dreapta turnului T, care are un număr de etaje strict mai mare decât turnul T;

Coeficientul de frumusețe al întregului ansamblu de turnuri este suma coeficienților de frumusețe avuţi de turnurile componente. Dezvoltatorul proiectului dorește să renunțe la unul dintre turnuri și să construiască în locul acestuia un restaurant subteran, acesta considerându-se un turn cu zero etaje. Dezvoltatorul dorește să calculeze coeficientul de frumusețe al ansamblului de turnuri, pentru fiecare posibilă amplasare a restaurantului.

Cerința

Cunoscând numărul N de turnuri și numărul etajelor fiecăruia, determinați coeficientul de frumusețe al ansamblului de turnuri pentru toate cele N posibilități de amplasare ale restaurantului, pe pozițiile 1, 2,…, N.

Date de intrare

Datele de intrare se citesc din fişierul turnuri.in, care are următoarea structură:
- pe prima linie se află numărul natural N, reprezentând numărul de turnuri;
- pe a doua linie se află N valori naturale nenule, separate prin câte un spațiu, reprezentând numărul etajelor turnurilor;

Date de ieșire

Datele de ieşire se vor scrie în fişierul turnuri.out, pe linii separate, astfel: pe linia i (1 ≤ i ≤ N) se găsește un număr natural reprezentând coeficientul de frumusețe al ansamblului dacă restaurantul s-ar construi în locul turnului i.

Restricții și precizări

• 1 ≤ N ≤ 100 000
• Numărul de etaje ale unui turn este un număr natural între 1 și 1 000 000 000
• Pentru teste în valoare de 30 de puncte, avem N ≤ 100
• Pentru teste în valoare de încă 30 de puncte, avem N ≤ 2000
• În concurs s-au acordat 10 puncte din oficiu. Aici se acordă pentru exemplul din enunț.

Exemplu:

turnuri.in

7
10 3 1 7 8 6 5

turnuri.out

19
22
22
22
21
22
22

Explicație

Figura 1 este reprezentarea grafică a fişierului de intrare.

Dacă restaurantul se construiește în locul turnului 1 (vezi figura 2), avem următorii coeficienți de frumusețe:
Restaurantul are coeficientul 1 (el însuși)
Turnul 2 are coeficientul 3 (secvența compusă din turnurile 1, 2 și 3)
Turnul 3 are coeficientul 1 (el însuși)
Turnul 4 are coeficientul 4 (secvența compusă din turnurile 1, 2, 3 și 4)
Turnul 5 are coeficientul 7 (secvența compusă din toate turnurile)
Turnul 6 are coeficientul 2 (secvența compusă din turnurile 6 și 7)
Turnul 7 are coeficientul 1 (el însuși)
Coeficientul de frumusețe al ansamblului este: 1 + 3 + 1 + 4 + 7 + 2 + 1 = 19