Fişierul intrare/ieşire:	compact3.in, compact3.out	Sursă	ONI 2019, clasele 11-12, ziua 2
Autor	Alex Tatomir	Adăugată de	Tinca Matei •TincaMatei
Timp execuţie pe test	0.7 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Compact3

Se dă un şir $a$ de $N$ numere naturale nenule mai mici sau egale cu $M$ . Se doreşte partiţionarea şirului în cât mai multe grupe stabile. O grupă stabilă se defineşte ca fiind o secvenţă continuă şi nevidă de numere $a_{s}, a_{(s + 1)}, a_{(s + 2)}, ..., a_{(d - 1)}, a_{d}$ , respectând următoarea condiţie:

orice alt element din afara intervalului $[s, d]$ este ori strict mai mare, ori strict mai mic decât toate valorile din $[s, d]$ .

Mai exact, pentru orice $i \notin [s, d]$ , doar una din următoarele condiţii este satisfăcută:

$a[i] < a[j]$ , oricare ar fi $s <= j <= d$ ;
$a[i] > a[j]$ , oricare ar fi $s <= j <= d$ .

Partiţionarea şirului presupune ca fiecare număr să facă parte din exact o grupă.

Cerinţă

Dându-se $N, M$ şi şirul $a$ de $N$ numere, să se găsească o partiţie a şirului $a$ în cât mai multe grupe stabile.

Date de intrare

În fişierul compact3.in, pe prima linie se află două numere $N$ şi $M$ separate prin spaţiu. Pe a doua linie se află cele $N$ elemente ale şirului $a$ separate prin câte un spaţiu.

Date de ieşire

În fişierul compact3.out se vor afişa două linii. Pe prima linie se va afla numărul maxim de grupe stabile $G$ , iar pe a doua linie se vor afla $G$ valori, reprezentând poziţia ultimului element al fiecărei grupe stabile în ordine crescătoare.

Restricţii

$1 \leq N \leq 1.000.000$ .
$1 \leq M \leq N$ .
$1 \leq a[i] \leq M$ , pentru $1 \leq i \leq N$ .
Pentru teste în valoare de 21 puncte $N \leq 100$ .
Pentru alte teste în valoare de 28 de puncte $N \leq 3000$ .
Se garantează că fiecare număr natural de la 1 la $M$ apare cel puţin o dată.
Ultimul indice din fiecare soluţie va fi întotdeauna $N$ .
În cazul în care există mai multe soluţii cu număr maxim de grupe stabile, se va afişa soluţia minimă lexicografic.
Un şir $a_1, a_2, ..., a_n$ este mai mic lexicografic decât un alt şir $b_1, b_2, ..., b_n$ dacă există un număr întreg $P$ mai mic sau egal cu $N$ astfel încât: $a_1 = b_1, a_2 = b_2, ..., a_{P - 1} = b_{P - 1}$ , iar $a_P < b_P$ .