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.

h2. Date de intrare

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

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.

h2. Date de ieşire

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

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

h2. Restricţii