StalinSort

Algoritmul StalinSort este un algoritm de sortare care este definit astfel in pseudocod:

def stalin_sort(A)
    dacă A este vid
        return A

    rezultat ← listă goală
    ultim ← A[1]
    adaugă ultim în rezultat

    pentru i ← 2 până la lungime(A)
        dacă A[i] ≥ ultim
            adaugă A[i] în rezultat
            ultim ← A[i]
        altfel
            continuă

    return rezultat

Cu alte cuvinte, algoritmul sterge de la stanga la dreapta toate valorile care sunt mai mici decat cea din stanga sa.

De exemplu, pentru $A = \{1, 4, 2, 3, 5\}$, algoritmul va returna $\{1, 4, 5\}$, fiindca sterge valorile $2$ si $3$ care nu sunt in ordine.

Cerință

Se da un sir de $N$ numere intregi, indexat de la $1$. Definim $F(i) =$ suma lungimilor tuturor sirurilor rezultate din aplicarea Stalin Sort asupra subsecventelor care incep in pozitia $i$. Sa se determine $F(1), F(2), \dots, F(N)$.

Date de intrare

Pe prima linie a fișierului de intrare stalinsort.in se gaseste numarul natural nenul $N$.

Pe a doua linie a fisierului de intrare stalinsort.in se vor gasi $N$ numere intregi, separate prin spații, reprezentând lista $A$.

Date de ieșire

Pe prima linie a fișierului de ieșire stalinsort.out se vor gasi $N$ numere naturale separate prin spații, al $i$-lea reprezentând $F(i)$.

Restricții și precizări

• $1 \leq N \leq 1\ 000\ 000$
• $-1\ 000\ 000\ 000 \leq A_i \leq 1\ 000\ 000\ 000$
• Se garanteaza ca raspunsurile pot fi reprezentate pe $64$ de biti cu semn.
• O subsecventa delimitata de capetele [l, r] a sirului $A$ este sirul $A'$, cu ${A'}_i = A_{l+i-1}$, cu $lungime(A') = r-l+1$. De exemplu, pentru $A = \{6, 5, 4, 7, 5\}$, subsecventa $[2, 4]$ a sirului $A$ este $A' = {5, 4, 7}$.
• Pentru teste in valoare de $10$ puncte: $A_i \leq A_{i+1}$
• Pentru alte teste in valoare de $10$ puncte: $A_i > A_{i+1}$
• Pentru alte teste in valoare de $15$ puncte: $N \leq 100$
• Pentru alte teste in valoare de $15$ puncte: $N \leq 1000$
• Pentru alte teste in valoare de $15$ puncte: $N \leq 100\ 000$, exista maximum $10$ pozitii pentru care $A_i \geq A_{i+1}$
• Pentru alte teste in valoare de $15$ puncte: $N \leq 100\ 000$

Exemplul 1

stalinsort.in

5
1 2 3 4 5

stalinsort.out

15 10 6 3 1

Explicație

stalin_sort([1, 1]) = {1}
stalin_sort([1, 2]) = {1, 2}
stalin_sort([1, 3]) = {1, 2, 3}
stalin_sort([1, 4]) = {1, 2, 3, 4}
stalin_sort([1, 5]) = {1, 2, 3, 4, 5}
Deci, $F(1) = 1 + 2 + 3 + 4 + 5 = 15$

stalin_sort([2, 2]) = {2}
stalin_sort([2, 3]) = {2, 3}
stalin_sort([2, 4]) = {2, 3, 4}
stalin_sort([2, 5]) = {2, 3, 4, 5}
Deci, $F(2) = 1 + 2 + 3 + 4 = 10$

stalin_sort([3, 3]) = {3}
stalin_sort([3, 4]) = {3, 4}
stalin_sort([3, 5]) = {3, 4, 5}
Deci, $F(3) = 1 + 2 + 3 = 6$

stalin_sort([4, 4]) = {4}
stalin_sort([4, 5]) = {4, 5}
Deci, $F(4) = 1 + 2 = 3$

stalin_sort([5, 5]) = {5}
Deci, $F(5) = 1$

Exemplul 2

stalinsort.in

5
4 6 1 3 5

stalinsort.out

9 4 6 3 1

Explicație

stalin_sort([1, 1]) = {4}
stalin_sort([1, 2]) = {4, 6}
stalin_sort([1, 3]) = {4, 6}
stalin_sort([1, 4]) = {4, 6}
stalin_sort([1, 5]) = {4, 6}
Deci, $F(1) = 1 + 2 + 2 + 2 + 2 = 9$

stalin_sort([2, 2]) = {6}
stalin_sort([2, 3]) = {6}
stalin_sort([2, 4]) = {6}
stalin_sort([2, 5]) = {6}
Deci, $F(2) = 1 + 1 + 1 + 1 = 4$

stalin_sort([3, 3]) = {1}
stalin_sort([3, 4]) = {1, 3}
stalin_sort([3, 5]) = {1, 3, 5}
Deci, $F(3) = 1 + 2 + 3 = 6$

stalin_sort([4, 4]) = {3}
stalin_sort([4, 5]) = {3, 5}
Deci, $F(4) = 1 + 2 = 3$

stalin_sort([5, 5]) = {5}
Deci, $F(5) = 1$