Masala E

Yer orbitasidagi Arxiv-Lentada ketma-ket joylashgan \(N\) ta yozuv bor. Har bir yozuv uchun \(a[i]\) qiymat berilgan (\(1..M\) oralig‘ida) — bu yozuvning maxfiylik darajasi.

Siz lentani ketma-ket bo‘laklarga ajratib, imkon qadar ko‘p mustaqil segment hosil qilmoqchisiz.

Mustaqil segment 

\([s,d]\) oralig‘idagi ketma-ket yozuvlar \(a[s], a[s+1], ..., a[d]\) mustaqil segment deyiladi, agar segmentdan tashqarida turgan har bir yozuv segment ichidagi yozuvlar bilan “aralashib” keta olmasa.

Aniqroq qilib aytganda, agar \(i\notin [s, d]\) bo‘lsa, unda quyidagi shartlardan aynan bittasi bajarilishi shart.

1. \(a[i]\) segment ichidagi barcha qiymatlardan kichik:
   \(a[i] < a[j]\) barcha \(s \le j \le d\) uchun;
2. \(a[i]\) segment ichidagi barcha qiymatlardan katta:
   \(a[i] > a[j]\) barcha \(s \le j \le d\) uchun;

Berilgan \(N, M\) va \(a\) ketma-ketligi uchun lentani ketma-ket segmentlarga ajrating:

• har bir indeks aynan bitta segmentga tegishli bo‘lsin;
• segmentlar soni maksimal bo‘lsin.

Natija sifatida:

1. maksimal segmentlar soni \(G\) ni chiqaring;
2. har bir segmentning oxirgi indeksi (\(d\) lar) ni o‘sish tartibida chiqaring.

Eslatma: oxirgi segmentning oxirgi indeksi doim \(N\) bo‘ladi.

Birinchi qatorda ikkita butun son - \(N, M\)beriladi: \((1\le N\le 10^6, 1\le M \le N)\)

Ikkinchi qatorda \(N\) ta butun son - \(a[1], a[2], ..., a[N]\) beriladi. \((1\le a[i] \le M, 1\le i \le N)\)

\([1, M]\) oralig‘idagi barcha qiymatlar ketma-ketlikda kamida bir marta uchraydi.

Birinchi qatorda bitta butun son - \(G\) (maksimal mustaqil segmentlar soni) ni chiqaring.

Ikkinchi qatorda \(G\) ta butun son chiqaring: \(d_1, d_2, ..., d_G\) (bu yerda \(d_k\) - \(k\)-segmentning oxirgi indeksi).

\((1 \le d_1 < d_2 < ... < d_G = N)\)