sortall

Pentru un şir de numere A se defineşte următoarea funcţie de cost:
$f(A) = 1 \cdot V_1 + 2 \cdot V_2 + \dots + K \cdot V_K$, unde $[V_1, V_2, \dots, V_K]$ sunt valorile distincte ale lui $A$, ordonate crescător.

Fiind dat un şir de $N$ numere naturale $A$, să se calculeze suma aplicării funcţiei $f$ pe toate subsecvenţele lui $A$ (i.e. $\sum_{i=1}^{n} \sum_{j=i}^{n} f(A[i \dots j])$) , unde $A[i \dots j]$ este subsecvenţa de la $i$ la $j$).

Date de intrare

Fişierul de intrare sortall.in conţine pe prima linie numărul natural $N$. Linia a doua conţine $N$ numere naturale separate prin spaţiu, reprezentând elementele şirului $A$.

Date de ieșire

În fişierul de ieşire sortall.out va conţine răspunsul modulo $1 \ 000 \ 000 \ 007$.

Restricții și precizări

• $1 \leq N \leq 50 \ 000$
• $1 \leq V_i \leq N$
• Pentru $10$ puncte $1 \leq N \leq 1 \ 000$
• Pentru alte $15$ puncte $1 \leq N \leq 5 \ 000$
• Pentru alte $20$ de puncte se garantează că valorile din şir sunt distincte

Exemplul 1

sortall.in

3
1 3 2

sortall.out

35

Exemplul 2

sortall.in

8
4 3 4 4 7 1 2 1

sortall.out

861