Dat fiind un șir de N numere naturale A[1], A[2], …, A[N], considerăm următorul algoritm, prezentat în pseudocod:

cnt ← 0
score ← 0
pentru i de la 1 la N executa
    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

Cerința

• Care este valoarea lui cnt la sfârșitul algoritmului?
• Care este valoarea lui 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], …, 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 ∈ {1, 2}
• 1 ≤ N ≤ 1.000.000
• 1 ≤ A_i ≤ 1.000.000.000 pentru oricare 1 ≤ i ≤ N
• Datorită dimensiunilor prea mari ale testelor din concurs, unele nu au fost adăugate

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 · 1 + 2 · 2 + 1 · 3 + 4 · 4 + 2 · 5 + 1 · 6 + 2 · 7 + 1 · 8 + 2 · 9 + 1 · 10 + 1 · 11