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

Poveste şi cerinţă...

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

h2. Date de intrare
 
Fişierul de intrare $leftmax.in$ ...

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.

h2. Date de ieşire

h2. Cerinţă

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

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

h2. Restricţii

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

h2. Exemplu

h2. Date de ieşire

table(example). |_. leftmax.in |_. leftmax.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

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

h3. Explicaţie

h2. 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$
 
h2. Exemple
 
table(example). |_. 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.
|

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