C. Нэмэх үү эс нэмэх үү

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

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

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

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

$n$ элементтэй $a_{1}, a_{2}, ..., a_{n}$ массив өгөгдөв. Таны олох ёстой зүйл бол хамгийн их давтагдсан тооны тоо юм.

Гэхдээ тийм тоог хайж эхлэхээс өмнө дараах үйлдлийг $k$-с хэтрэхгүй удаа гүйцэтгэж болно. Энэ үйлдэл нь: Дурийн элементийг сонгон түүн дээр нэгийг нэмнэ. Өөрөөр хэлбэл нэг элементийг $k$-с илүүгүй нэмэгдүүлж болно (Нэг элемент нь дээрээ дахин энэ үйлдлээ хийж болно).

Таны олох зүйл бол $k$-с илүүгүй удаа 'үйлдлийг' массив дээр гүйцэтгэж хамгийн их давтагдсан тооны тоог максимумчлах юм. Хэрвээ олон хариу байвал хамгийн бага тоог нь ол.

Оролт

Эхний мөрөнд 2 бүхэл тоо болох $n$ болон $k$ ($1 ≤ n ≤ 10^{5}$; $0 ≤ k ≤ 10^{9}$) массивийн элементийн тоо, үйлдлийг ашиглаж болох тоо.

Дараа нь $n$ ширхэг массивийн элементүүд $a_{1}, a_{2}, ..., a_{n}$ $(|a_{i}| ≤ 10^{9})$

Гаралт

2 бүхэл тоо зайгаар тусгаарлан хэвлэнэ. $k$ үйлдэл хийсэний дараа хамгийн их давтагдсан тооны тоо болон хамгийн их давтагдсан тооны хамгийн бага утга.

Орчуулсан: anhaabc

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

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

Тэмдэглэл

Эхний жишээ нь дээр хоёр дахь элементийг 1 удаа, тав дахь элементийг 2 удаа нэмэгдүүлсэн байна. Тэгээд $6, 4, 4, 0, 4$ ийм болгосноор $4$ гэсэн тоо $3$-н удаа давтагдсан байна.

Хоёр дахь жишээ нь дээр ямар ч үйлдэл хийх хэрэггүй. Гурвууланг нь нэгээр нэмэгдүүлж $6, 6, 6$ болгож болох ч бодлогийн нөхцөлөөр $6$ биш $5$-г авах ёстой.

Гурав дахь жишээний хувьд 2 дахь элемент, 5 дахь элементийг тус тус 1-ээр нэмэгдүүлж $3, 2, 2, 2, 2$ ийм болгосноор $2$-н тоог $4$ удаа гаргаж авч байна.

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