changemin

Dat fiind un șir de $N$ numere naturale $A_1, A_2, \ldots, A_N$, considerăm următorul algoritm, prezentat în pseudocod:

cnt ← 0
score ← 0
pentru i de la 1 la N execută
    min ← ∞
    pentru j de la i la N executa
        daca A[j] < min atunci
            min ← A[j]
            cnt ← cnt + 1
            score ← score + cnt · A[j]
        sfarsit_daca
     sfarsit_pentru
sfarsit_pentru

• Care este valoarea lui $\mathit{cnt}$ la sfârșitul algoritmului?
• Care este valoarea lui $\mathit{score}$ la sfârșitul algoritmului, modulo $666 \ 013$?

Date de intrare

Pe prima linie a fișierului de intrare changemin.in se află numerele naturale $T$ și $N$, separate printr-un spațiu, reprezentând cerința care trebuie rezolvată, respectiv numărul de numere ce urmează a fi citite.

Pe următoarea linie se află $N$ numere naturale separate printr-un spațiu, reprezentând numerele $A_1, A_2, \ldots, A_N$.

Date de ieșire

Fișierul de ieșire changemin.out va conține:

• Pentru $T = 1$: un singur număr natural, reprezentând valoarea lui $cnt$ la finalul execuției algoritmului;
• Pentru $T = 2$: un singur număr natural, reprezentând valoarea lui $score$ la finalul execuției algoritmului, modulo $666 \ 013$.

Restricții și precizări

• $T \in \{1, 2\}$
• $1 \leq N \leq 1 \ 000 \ 000$
• $1 \leq A_i \leq 1 \ 000 \ 000 \ 000$ pentru oricare $1 \leq i \leq N$

Exemplul 1

changemin.in

1 5
3 4 2 2 1

changemin.out

11

Explicație

$cnt$ este incrementată de $11$ ori pe parcursul execuției algoritmului

Exemplul 2

changemin.in

2 5
3 4 2 2 1

changemin.out

103

Explicație

$score$ este obținută astfel: $score = 3 \cdot 1 + 2 \cdot 2 + 1 \cdot 3 + 4 \cdot 4 + 2 \cdot 5 + 1 \cdot 6 + 2 \cdot 7 + 1 \cdot 8 + 2 \cdot 9 + 1 \cdot 10 + 1 \cdot 11$