Fişierul intrare/ieşire:leftmax.in, leftmax.outSursăOJI 2020, clasa a 10-a
AutorTamio-Vesa NakajimaAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test0.7 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/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.inleftmax.outExplicaţ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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?