| Fişierul intrare/ieşire: | sortall.in, sortall.out | Sursă | Lot Seniori Campulung 2018, baraj 3 |
| Autor | Adrian Budau, Bogdan Ciobanu, Tamio-Vesa Nakajima | Adăugată de |  Coman Andrei •andreicoman299 |
| Timp execuţie pe test | 3 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | sortall.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
