C. Хосыг ол

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

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

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

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

$n$ элэменттэй $a_1, a_2, a_n$ бүхэл тоонуудын дарааллыг авч үзье (Элемэнтүүд нь ялгаатай байх албагүй). Энэ бодлогод энэ массиваас үүсгэж болох бүх $n^2$ хосууд болох ($a_i,a_j$), ($1<=i,j<=n$) -г авч үзнэ.

Жишээ нь $a={3,1,5}$ дарааллаас $(3,3)$, $(3,1)$, $(3,5)$, $(1,3)$, $(1,1)$, $(1,5)$, $(5,3)$, $(5,1)$, $(5,5)$ хосууд үүснэ.

Бүх хосуудыг үл буурах эрэмбээр эрэмбэлье. Үүнд ($p_1 < p_2$) эсвэл ($p_1 = p_2$ ба $q_1 < q_2$) нөхцлийг хангасан тохиолдолд ($p_1,q_1$)-ийг ($p_2,q_2$)-ээс бага гэж үзнэ.

Жишээ нь дээр өгөгдсөн дараалал дараах байдлаар эрэмбэлэгдэнэ. $(1,1)$, $(1,3)$, $(1,5)$, $(3,1)$, $(3,3)$, $(3,5)$, $(5,1)$, $(5,3)$, $(5,5)$.

Эрэмблэгдсэн дарааллыг $1$-ээс $n^2$ хүртэл дугаарласан гэж үзвэл $k$ дах хосыг олно уу.

Оролт

Эхний мөрөнд $n$ ба $k$ $(1≤n≤10^5, 1≤k≤n^2)$ өгөгдөнө. Хоёр дах мөрөнд анх өгөгдсөн дараалал болох $n$ элэменттэй дараалал $a_1,a_2,...,a_n$ ($-10^9≤a_i≤10^9$) өгөгдөнө. Дараалалд ижил тоонууд байж болох ба тоонууд хоосон зайгаар тусгаарлагдсан байна.

C++ хэл ашиглаж байгаа бол 64-бит тоо уншихдаа %lld ашиглахын оронд cin, cout, streams, %I64d зэргийг ашиглана уу!

Гаралт

Нэг мөрөнд олдсон $k$ дах хосын хоер тоог хэвлэ.

Орчуулсан: Б.Батхуяг

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

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

Тэмдэглэл

In the first sample the sorted sequence for the given array looks as: $(1, 1), (1, 2), (2, 1), (2, 2)$. The $4$-th of them is pair $(2, 2)$.

The sorted sequence for the array from the second sample is given in the statement. The $2$-nd pair there is $(1, 3)$.

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