snpid

Se dau $N$ puncte în plan, numerotate de la $1$ la $N$. Punctul $i$ are coordonatele $(i, y(i))$, iar cele $N$ coordonate $y$ formează o permutare a numerelor de la $1$ la $N$. Un dreptunghi frumos este un dreptunghi ce are în colţurile stânga-jos şi dreapta-sus două dintre cele $N$ puncte. Mai exact, două puncte $i$ şi $j$ determină un dreptunghi frumos cu colţul stânga-jos în punctul $i$ şi colţul dreapta-sus în punctul $j$ dacă $i < j$ şi $y(i) < y(j)$. Fie $NPID(i, j)$ numărul de puncte aflate strict în interiorul dreptunghiului frumos cu colţul stânga-jos în punctul $i$ şi colţul dreapta-sus în punctul $j$.

Cerință

Determinaţi pentru fiecare punct $i$ valoarea $SNPID(i)$ = suma tuturor valorilor $NPID(i, j)$ posibile (adică suma numerelor de puncte aflate în interiorul dreptunghiurilor frumoase cu colţul stânga-jos în punctul i).

Date de intrare

Pe prima linie a fişierului snpid.in se afla numărul natural $N$, reprezentând numărul de puncte. Pe următoarea linie se află $N$ numere naturale, valorile $y(1), y(2), \dots, y(N)$ în această ordine.

Date de ieșire

Fişierul snpid.out va conţine $N$ linii, ce-a de-a $i$-a linie conţinând valoarea $SNPID(i)$.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$
• Atenţie! Rezultatele pot depăşi tipurile de date întregi pe $32$ de biţi.

Exemplu

snpid.in

12
3 1 4 11 7 12 2 9 10 5 8 6

snpid.out

16
21
8
0
1
0
3
0
0
0
0
0