Fişierul intrare/ieşire:sortall.in, sortall.outSursăLot Seniori Campulung 2018, baraj 3
AutorAdrian Budau, Bogdan Ciobanu, Tamio-Vesa NakajimaAdăugată deandreicoman299Coman Andrei andreicoman299
Timp execuţie pe test6 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sortall

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

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

  • 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

Exemplu

sortall.insortall.out
3
1 3 2
35
8
4 3 4 4 7 1 2 1
861
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?