Sam

sam

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

Aranjăm primele $N$ numere naturale nenule sub forma unui şir $A[~1~], A[~2~], ..., A[~N~]$. Fie $X[~1~], X[~2~],...,X[~K~] (K ≥ 3)$, un subşir al şirului $A$.
Numim "extrem local" al subşirului $X$ termenul din mijlocul unei secvenţe de lungime trei din subşir, $X[~i-1~], X[~i~], X[~i+1~]$, cu proprietatea: $X[~i-1~] < X[~i~] > X[~i+1~]$ sau $X[~i-1~] > X[~i~] < X[~i+1~], 1 < i < K$.
Vom nota cu $nrex(X)$ numărul de extreme locale ale subşirului $X$.
Spunem că un subşir $X[~1~], X[~2~],...,X[~K~] ( K ≥ 2)$ al şirului $A$ este subşir alternant dacă $nrex(X)=K-2$, adică exceptând primul şi ultimul termen din subşir toţi ceilalţi termeni sunt extreme locale ale subşirului $X$.
Dintre toate subşirurile alternante ale şirului $A$ ne interesează cele de lungime maximă pe care le vom numi subşiruri alternante maximale.

Aranjăm primele $N$ numere naturale nenule sub forma unui şir A[~1~], A[~2~], ..., A[~N~]. Fie X[~1~], X[~2~],...,X[~K~] (K ≥ 3), un subşir al şirului A.
Numim "extrem local" al subşirului X termenul din mijlocul unei secvenţe de lungime trei din subşir, X[~i-1~], X[~i~], X[~i+1~], cu proprietatea: X[~i-1~] < X[~i~] > X[~i+1~] sau X[~i-1~] > X[~i~] < X[~i+1~], 1 < i < K.
Vom nota cu nrex(X) numărul de extreme locale ale subşirului X.
Spunem că un subşir X[~1~], X[~2~],...,X[~K~] ( K ≥ 2) al şirului A este subşir alternant dacă nrex(X)=K-2, adică exceptând primul şi ultimul termen din subşir toţi ceilalţi termeni sunt extreme locale ale subşirului X.
Dintre toate subşirurile alternante ale şirului A ne interesează cele de lungime maximă pe care le vom numi subşiruri alternante maximale.

h2. Cerinţă

Cunoscând $N$ şi tabloul $A$ se cere să se determine restul obţinut la împărţirea dintre numărul $M$ al subşirurilor alternante maximale ale tabloului $A$ şi numărul **1000003**.

Cunoscând $N$ şi tabloul A se cere să se determine restul obţinut la împărţirea dintre numărul $M$ al subşirurilor alternante maximale ale tabloului A şi numărul **1000003**.

h2. Date de intrare

h2. Restricţii

* $3 ≤ N ≤ 100000$

* $3 ≤ $N$ ≤ 100000$

h2. Exemplu

h3. Explicaţie

Şirul dat conţine trei extreme locale, valorile $5, 4$ şi $7$. Cele şase subşiruri alternante maximale cu şirul dat sunt:
$1 5 4 6 2, 1 5 4 7 2, 1 5 4 7 6,$
$3 5 4 6 2, 3 5 4 7 2, 3 5 4 7 6$

Şirul dat conţine trei extreme locale, valorile 5, 4 şi 7. Cele şase subşiruri alternante maximale cu şirul dat sunt:
1 5 4 6 2, 1 5 4 7 2, 1 5 4 7 6,
3 5 4 6 2, 3 5 4 7 2, 3 5 4 7 6

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