B. Массив

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

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

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

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

Чамд $a_{1}, a_{2}, ..., a_{n}$ гэсэн $n$ ширхэг бүхэл тоонуудаас бүтсэн $a$ массив өгөгдөв. Чиний даалгавар бол агуулгаараа хамгийн бага байх $[l, r]$ $(1 ≤ l ≤ r ≤ n)$ гэсэн хэсэг олох ба энэ нь $a_{l},  a_{l + 1},  ...,  a_{r}$ гэсэн тоонууд дунд яг $k$ ширхэг ялгаатай тоо орсон байх ёстой.

$[l, r]$ ($1 ≤ l ≤ r ≤ n;$ $l, r$ нь бүхэл тоо) хэсгийн урт нь $m = r - l + 1$ байх яг $k$ ширхэг ялгаатай тоо орсон ба агуулгаараа хамгийн бага байх гэсэн нөхцлийг хангахын тулд $m$-ээс бага урттай $1 ≤ l ≤ x ≤ y ≤ r ≤ n$ байх ба яг $k$ ширхэг ялгаатай тоо орсон $[x, y]$ хэсэг олдохгүй байх явдал юм. Мөн хариу болох $[l, r]$ хэсэг нь дээрх чанарыг хангах хэсгүүд дундаас хамгийн богино нь байх албагүйг анхаарна уу.

Оролт

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

Гаралт

$[l, r]$ завсар нь бодлогын хариу болдог байх $l$ ба $r$ ($1 ≤ l ≤ r ≤ n$) гэсэн хос бүхэл тоог зайгаар тусгаарлан хэвлэнэ. Хэрэв тийм хэсэг олдохгүй бол "$-1$" (хашилтгүйгээр) хэвлэ. Олон хариу байвал дурын нэгийг нь хэвлэ.

Орчуулсан: Жавхлан

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

Оролт
4 2
1 2 2 3
Гаралт
1 2
Оролт
8 3
1 1 2 2 3 3 4 5
Гаралт
2 5
Оролт
7 4
4 7 7 4 7 4 7
Гаралт
-1 -1

Тэмдэглэл

Эхний жишээн дээр $a_{1}$ ба $a_{2}$ нь яг хоёр ялгаатай тоо байна.

Хоёр дахь жишээн дээр $[2, 5]$ хэсэг нь яг 3 ялгаатай тоо орсон агуулгаараа хамгийн бага нь юм. Гэхдээ энэ нь хариу болж чадах хэсгүүдээс хамгийн богино нь биш.

Гуравдугаар жишээн дээр 4н ялгаатай тоо агуулсан хэсэг байхгүй.

Сэтгэгдлүүдийг ачааллаж байна...