compact

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 ∉ [s,d], doar una din următoarele condiții este satisfăcută:

1. a[i] < a[j], oricare ar fi s <= j <= d;
2. 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

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 compact.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 ≤ N ≤ 1.000.000.
• 1 ≤ M ≤ N.
• 1 ≤ a[i] ≤ M, pentru 1 ≤ i ≤ N.
• Pentru teste în valoare de 21 puncte N ≤ 100.
• Pentru alte teste în valoare de 28 de puncte N ≤ 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$.
• Precizare: 3 dintre teste nu au fost disponibile și au fost eliminate.

Exemplu

compact.in

6 5
1 4 2 3 5 5

compact.out

5
1 2 3 4 6

compact.in

7 5
1 3 2 1 5 2 4

compact.out

1
7

compact.in

14 10
5 8 6 7 5 2 1 2 3 3 4 10 9 10

compact.out

5
5 8 10 11 14

compact.in

4 3
3 1 2 1

compact.out

2
1 4