== include(page="template/taskheader" task_id="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.

Poveste şi cerinţă...

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 intrare

h2. Cerinţă

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

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. Date de ieşire

h2. Date de intrare

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

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

h2. Date de ieşire

* $... ≤ ... ≤ ...$
 
h2. Exemplu

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

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

h2. Restricţii şi precizări

h3. Explicaţie

* $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") ==