Fişierul intrare/ieşire:sam.in, sam.outSursăLot Sovata 2014 - Baraj 2 Juniori
AutorIonel-Vasile Pit-RadaAdăugată deAlexandruValeanuAlexandru Valeanu AlexandruValeanu
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sam

Aranjăm primele N numere naturale nenule sub forma unui şir A1, A2, ..., AN. Fie X1, X2,...,XK (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, Xi-1, Xi, Xi+1, cu proprietatea: Xi-1 < Xi > Xi+1 sau Xi-1 > Xi < Xi+1, 1 < i < K.
Vom nota cu nrex(X) numărul de extreme locale ale subşirului X.
Spunem că un subşir X1, X2,...,XK ( 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

sam.insam.out
7
1 3 5 4 7 6 2
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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?