sam

Aranjăm primele $N$ numere naturale nenule sub forma unui șir $A_1, A_2, \dots, A_N$.

Fie $X_1, X_2, \dots, X_K$, ($K \geq 3$), un subșir al șirului $A$. Numim extrem local al subșirului $X$ termenul din mijlocul unei secvențe de lungime $3$ din subșir, $X_{i-1}, X_i, X_{i+1}$, cu proprietatea:
$X_{i-1} < X_i > X_{i+1}$, $1 < i < K$
sau
$X_{i-1} > X_i < X_{i+1}$, $1 < i < K$.

Vom nota cu $\text{nrex}(X)$ numărul de extreme locale ale subșirului $X$. Spunem că un subșir $X_1, X_2, \dots, X_K$, ($K \geq 2$) al șirului A este subșir alternant dacă $\text{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.

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 $1 \ 000 \ 003$.

Date de intrare

Fişierul de intrare sam.in conţine pe prima linie numărul natural $N$. Pe linia a doua se găsesc cele $N$ numere ale șirului dat separate prin câte un spațiu.

Date de ieșire

În fişierul de ieşire sam.out se va scrie numărul obţinut ca rest la împărţirea dintre numărul $M$, având semnificația descrisă mai sus, şi numărul $1 \ 000 \ 003$.

Restricții și precizări

• $3 \leq N \leq 100 \ 000$;

Exemplu

sam.in

7
1 3 5 4 7 6 2

sam.out

6

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