D. Хамгийн урт дэд дараалал

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Танд $n$ элементтэй $a$ массив болон $m$ тоо өгөгдөнө. $a$ массиваас дэд дараалал үүсгэж уг дэд дарааллын гишүүдийн ХБЕХ-г ол. Энэ ХБЕХ-г $l$-р тэмдэглэвэл $l ≤ m$ байх $a$ массиваас үүсч болох дэд дарааллуудаас хамгийн урт дэд дарааллыг ол.

Дэд дараалал нь $a$ массивын зарим элементийг устгах замаар үүсгэсэн массив байна. Бүх элементийг устгаж болох ба нэг ч элемент устгахгүй байж бас болно.

Хоосон массивын хувьд ХБЕХ нь $1$ байна.

Оролт

Эхний мөрөнд хоёр ширхэг бүхэл тоон утга $n$ ба $m$ байх ба харгалзан $a$ массивын хэмжээ болон бодлогын нөхцөл болох тоо юм. $(1 ≤ n, m ≤ 10^6)$

Хоёр дахь мөрөнд $n$ ширхэг бүхэл тоон утга $a_{i}$ байх ба эдгээр нь $a$ массивын элементүүд юм. $(1 ≤ a_{i} ≤ 10^9)$

Гаралт

Эхний мөрөнд хоёр бүхэл тоон утга $l$ ба $k_{max}$ байх ба харгалзан ХБЕХ-н утга болон хамгийн тохиромжтой дэд дарааллын элементийн тоо юм. ($1 ≤ l ≤ m, 0 ≤ k_{max} ≤ n$)

Хоёр дахь мөрөнд $k_{max}$ ширхэг бүхэл тоон утга байх ба дэд дарааллын элементүүдийн $a$ массив дахь байрлалыг өсөхөөр эрэмбэлэн хэвлэнэ.

Та байж болох хамгийн их урттай дэд дарааллуудаас алийг нь ч хэвлэсэн болно.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
7 8
6 2 9 2 7 2 3
Гаралт
6 5
1 2 4 6 7
Оролт
6 4
2 2 2 3 3 3
Гаралт
2 3
1 2 3
Сэтгэгдлүүдийг ачааллаж байна...