Fișierul intrare/ieșire | sam.in, sam.out | Sursă | Lot Sovata 2014 - Baraj 2 |
---|---|---|---|
Autor | Ionel-Vasile Piț-Rada | Adăugată de | Tinca Matei • TincaMatei |
Timp de execuție pe test | 0.6 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Sam (Lot Juniori)
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 la 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 la numărul 1000003.
Restricții
- 3 ≤ N ≤ 100000
Exemplu
sam.in | sam.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