Fișierul intrare/ieșire sam.in, sam.out Sursă Lot Sovata 2014 - Baraj 2
Autor Ionel-Vasile Piț-Rada Adăugată de avatar TincaMatei Tinca Matei TincaMatei
Timp de execuție pe test 0.6 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii