Fişierul intrare/ieşire:	sam.in, sam.out	Sursă	Lot Sovata 2014 - Baraj 2 Juniori
Autor	Ionel-Vasile Pit-Rada	Adăugată de	Alexandru Valeanu •AlexandruValeanu
Timp execuţie pe test	0.15 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Sam

Aranjăm primele N numere naturale nenule sub forma unui şir A₁, A₂, ..., A_N. Fie X₁, X₂,...,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₁, X₂,...,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ţă

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

• 3 ≤ N ≤ 100000

Exemplu

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 

Cum se trimit solutii?