| Fişierul intrare/ieşire: | leftmax.in, leftmax.out | Sursă | OJI 2020, clasa a 10-a |
| Autor | Tamio-Vesa Nakajima | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Leftmax
În clasa lui Dexter sunt N elevi de înălţimi distincte. La ora de sport, ei sunt aşezaţi în linie, de la stânga la dreapta. Profesorul lor, Johnny, va selecta pentru un exerciţiu elevi aflaţi pe poziţii consecutive în linie, astfel încât cel mai înalt elev dintre cei selectaţi să se afle în prima jumătate a acestora.
De exemplu, dacă elevii au, în ordine, înălţimile 1, 5, 4, atunci profesorul poate să îi selecteze pe cei cu înălţimile 5 şi 4, dar nu poate să îi selecteze pe cei cu înălţimile 1 şi 5. Desigur, există mai multe moduri de a selecta elevii astfel încât să fie satisfăcută condiţia de mai sus. Profesorul Johnny ar vrea să afle în câte moduri se poate face acest lucru.
Cerinţă
Dându-se N şi înălţimile elevilor din clasă, aflaţi în câte moduri pot fi selectaţi oricâţi elevi aflaţi pe poziţii consecutive, astfel încât să fie îndeplinită condiţia din enunţ.
Date de intrare
Fişierul de intrare leftmax.in conţine, pe prima linie, numărul N, iar pe a doua linie înălţimile elevilor în ordinea în care sunt aşezaţi în linie.
Date de ieşire
Fişierul de ieşire leftmax.out conţine pe prima linie răspunsul la cerinţă, sub formă de rest al împărţirii la 1.000.000.007 (modulo 1.000.000.007).
Restricţii şi precizări
- 1 ≤ N ≤ 100.000
- 1 ≤ înălţimea oricărui elev ≤ N
- Dacă se selectează un număr impar de elevi, atunci considerăm că cel din mijlocul selecţiei se află în prima jumătate a elevilor selectaţi
- Pentru 10 puncte, N ≤ 1.000 şi elevii sunt ordonaţi descrescător după înălţime
- Pentru alte 35 de puncte, N ≤ 1.000
- Pentru alte 20 de puncte, N ≤ 30.000
Exemple
| leftmax.in | leftmax.out | Explicaţie |
|---|---|---|
| 4 1 4 2 3 | 8 | Sunt 4 moduri de a selecta câte un singur elev. Este un singur mod de a selecta câte doi elevi (cei cu înălţimile 4, 2). Sunt 2 moduri de a selecta câte 3 elevi (cu înălţimile 4, 2, 3 şi 1, 4, 2). Este un singur mod de a selecta toţi cei 4 elevi. În total sunt 8 modulo 1.000.000.007 = 8 moduri. |
| 7 1 2 3 4 5 6 7 | 7 | Se pot selecta doar câte un singur elev. |
| 7 7 6 5 4 3 2 1 | 28 | Se pot selecta oricâţi elevi pe poziţii consecutive. |
