E. Үзэсгэлэн

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

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

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

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

Бэрландын нэрт зохиолч Бэрлбуригийн 50 насны ой болоход хэдхэн өдөр үлджээ. Хотын номын сангаас нэрт зөгнөлт зохиолчийн бүтээлүүдээр үзэсгэлэн гаргахаар шийдэв. Ингэхдээ зөвхөн тодорхой хугацааны хооронд хэвлэгдсэн номнуудыг хэвлэх нь дээр гэж үзжээ. Номнуудын хэмжээ хэтэрхий ялгаатай байх нь үзэгчдэд тааламжгүй байдаг тул зохион байгуулагчид хамгийн өндөр болон намхан хоёр номын өндрийн ялгаа нь $k$ миллиметрээс ихгүй байлгахаар тогтов.

Номын санд Бэрлбуригийн $n$ ном байх бөгөөд хэвлэгдсэн дарааллаар байрлажээ. Ном бүрийн өндөр миллиметрээр мэдэгдэж байгаа бөгөөд $h_i$ гэж тэмдэглэе. Зохиолч Бэрлбури үнэхээр их алдартай тул зохион байгуулагчид аль болох олон ном багтаахыг хүсчээ. Тэгээд аль он дарааллын хоорондох номнуудыг сонговол хамгийн олон ном үзэсгэлэнд тавьж болохыг сонгож өгнө үү гэж танаас хүсжээ.

Оролт

Эхний мөрөнд номын санд байгаа Бэрлбуригийн номнуудын тоо $n$ болон хамгийн өндөр хамгийн намхан хоёр номын өндрийн зөрүүний байж болох хамгийн их утга $k$ тоо байна. ($1 ≤ n ≤ 10^5; 0 ≤ k ≤ 10^6$)

Хоёр дахь мөрөнд $n$ ширхэг $i$-р номны өндрийг илэрхийлэх $h_i$ ($1 ≤ h_i ≤ 10^6$) тоо хоосон зайгаар тусгаарлагдан байна.

Гаралт

Эхний мөрөнд $a$, $b$ хоёр тоо хоосон зайгаар тусгаарлагдан байна.

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

$b$ - сонгож болох он дарааллын нийт тоо.

Дараагийн $b$ мөрөнд мөр тус бүрт боломжит номнуудын дарааллыг илтгэх эхний номны болон сүүлчийн номны дугаар байрлана.

Орчуулсан: gmunkhbaatarmn

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

Оролт
3 3
14 12 10
Гаралт
2 2
1 2
2 3
Оролт
2 0
10 10
Гаралт
2 1
1 2
Оролт
4 5
8 19 10 13
Гаралт
2 1
3 4
Сэтгэгдлүүдийг ачааллаж байна...