sortall

Sortall

== include(page="template/taskheader" task_id="sortall") ==

Poveste şi cerinţă...

Pentru un şir de numere $A$ se defineşte următoarea funcţie de cost:
$f(A) = 1 * V1 + 2 * V2 + ... + K * VK$, unde $[V1, V2, ..., VK]$ 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. suma după $(1 ≤ i ≤ j ≤ N)$ din $f(A[i...j])$, unde $A[i…j]$ este subsecvenţa de la $i$ la $j$).

h2. Date de intrare

Fişierul de intrare $sortall.in$ ...

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$.

h2. Date de ieşire

În fişierul de ieşire $sortall.out$ ...

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

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 50000$
* $1 ≤ Vi ≤ N$
* Pentru $10$ puncte $1 ≤ N ≤ 1000$
* Petru alte $15$ puncte $1 ≤ N ≤ 5000$
* Petru alte $20$ de puncte se garantează că valorile din şir sunt distincte

h2. Exemplu
table(example). |_. sortall.in |_. sortall.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie

| 3
  1 3 2
| 35
|
| 8
  4 3 4 4 7 1 2 1
| 861
|

...

== include(page="template/taskfooter" task_id="sortall") ==