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], 1<i<K 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.

Cerința

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.

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

Restricții și precizări

• 3 ≤ N ≤ 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)