== include(page="template/taskheader" task_id="compact3") ==
Poveste şi cerinţă...
Se dă un şir <tex>a</tex> de <tex>N</tex> numere naturale nenule mai mici sau egale cu <tex>M</tex>. 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 <tex>a_{s}, a_{(s + 1)}, a_{(s + 2)}, ..., a_{(d - 1)}, a_{d}</tex>, respectând următoarea condiţie:
* orice alt element din afara intervalului <tex>[s, d]</tex> este ori strict mai mare, ori strict mai mic decât *toate* valorile din <tex>[s, d]</tex>.
Mai exact, pentru orice <tex>i \notin [s, d]</tex>, doar una din următoarele condiţii este satisfăcută:
# <tex>a[i] < a[j]</tex>, oricare ar fi <tex>s <= j <= d</tex>;
# <tex>a[i] > a[j]</tex>, oricare ar fi <tex>s <= j <= d</tex>.
Partiţionarea şirului presupune ca fiecare număr să facă parte din *exact o grupă*.
h2. Cerinţă
Dându-se <tex>N, M</tex> şi şirul <tex>a</tex> de <tex>N</tex> numere, să se găsească o partiţie a şirului <tex>a</tex> în cât mai multe grupe stabile.
h2. Date de intrare
Fişierul de intrare $compact3.in$ ...
În fişierul $compact3.in$, pe prima linie se află două numere <tex>N</tex> şi <tex>M</tex> separate prin spaţiu. Pe a doua linie se află cele <tex>N</tex> elemente ale şirului <tex>a</tex> separate prin câte un spaţiu.
h2. Date de ieşire
În fişierul de ieşire $compact3.out$ ...
În fişierul $compact3.out$ se vor afişa două linii. Pe prima linie se va afla numărul maxim de grupe stabile <tex>G</tex>, iar pe a doua linie se vor afla <tex>G</tex> valori, reprezentând poziţia ultimului element al fiecărei grupe stabile în *ordine crescătoare*.
h2. Restricţii
* $... ≤ ... ≤ ...$
* <tex>1 \leq N \leq 1.000.000</tex>.
* <tex>1 \leq M \leq N</tex>.
* <tex>1 \leq a[i] \leq M</tex>, pentru <tex>1 \leq i \leq N</tex>.
* Pentru teste în valoare de 21 puncte <tex>N \leq 100</tex>.
* Pentru alte teste în valoare de 28 de puncte <tex>N \leq 3000</tex>.
* Se garantează că fiecare număr natural de la 1 la <tex>M</tex> apare cel puţin o dată.
* Ultimul indice din fiecare soluţie va fi întotdeauna <tex>N</tex>.
* Î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 <tex>a_1, a_2, ..., a_n</tex> este mai mic lexicografic decât un alt şir <tex>b_1, b_2, ..., b_n</tex> dacă există un număr întreg <tex>P</tex> mai mic sau egal cu <tex>N</tex> astfel încât: <tex>a_1 = b_1, a_2 = b_2, ..., a_{P - 1} = b_{P - 1}</tex>, iar <tex>a_P < b_P</tex>.
h2. Exemplu
table(example). |_. compact3.in |_. compact3.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
| 6 5
1 4 2 3 5 5
| 5
1 2 3 4 6
|
| 7 5
1 3 2 1 5 2 4
| 1
7
|
| 14 10
5 8 6 7 5 2 1 2 3 3 4 10 9 10
| 5
5 8 10 11 14
|
| 4 3
3 1 2 1
| 2
1 4
|
== include(page="template/taskfooter" task_id="compact3") ==
