Fişierul intrare/ieşire:	snpid.in, snpid.out	Sursă	Lot Resița 2012 - Baraj 2 Seniori
Autor	Mugurel Ionut Andreica	Adăugată de	Simoiu Robert •SpiderMan
Timp execuţie pe test	0.4 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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(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

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

Exemplu

Cum se trimit solutii?