C. Дундах утга

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

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

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

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

$n$ урттай массивын дундах утга гэдэг нь массивын элементүүдийг үл буурах дарааллаар ($1$-ээс эхлэн дугаарлана) эрэмбэлсний дараах $\lfloor\frac{n+1}{2}\rfloor$-р байрлал дахь элемент юм. $(2, 6, 1, 2, 3)$ массивын дундах утга нь $2$, $(0, 96, 17, 23)$ массивын дундах утга нь $17$ байна.

$\lfloor\frac{a}{b}\rfloor$ гэдэг нь $a$ тоог $b$ тоонд хуваагаад гарсан бүхэл хэсгийг авахыг хэлнэ.

Нэгэн өдөр Вася Петяд $n$ бүхэл тоонуудаас бүрдсэн массивыг үзүүлж, массивын дундах утгыг олохыг санал болгожээ. Гэтэл Петя массивыг ч харалгүйгээр дундах утга $x$-тэй тэнцүү гэж хэлжээ. Петя их шударга хүү учраас үр дүнд нь үүссэн массивын дундах утга нь $x$-тэй тэнцүү байхаар анх өгөгдсөн массив дээр хэд хэдэн тоо нэмэхээр шийджээ.

Петя массив дээр $1$-ээс $10^{5}$ хүртэлх бүхэл тоонуудаас нэмж болох ба нэг тоог хэд хэдэн удаа нэмж болно. Бас нэг ч тоо нэмэхгүй байж болно. Мөн массивын анхны элементүүдийн утгыг өөрчилж болохгүй.

Вася өөр зүйлд анхаарлаа хандуулаад завгүй байх хооронд Петя түүнд хэрэгтэй байгаа элементүүдийн хамгийн бага тоог олохыг танаас хүсч байна.

Оролт

Оролтын эхний мөр нь хоорондоо зайгаар тусгаарлагдсан $n$, $x$ ($1 ≤ n ≤ 500$, $1 ≤ x ≤ 10^{5}$) бүхэл тоонуудыг агуулна. Эдгээр нь анхны массивын урт болон шаардсан дундах утга юм. Хоёр дахь мөр нь анхны массив болох зайгаар тусгаарлагдсан $n$ тоонуудыг агуулна. Массивын элементүүд нь $1$-ээс $10^{5}$ хүртэлх бүхэл тоонуудаас бүрдэх ба заавал ялгаатай тоонууд байх албагүй.

Гаралт

Нэг бүхэл тоо хэвлэнэ. Энэ нь Петя массивын дундах утгыг $x$ байлгахын тулд массив дээр нэмэх хэрэгтэй элементүүдийн хамгийн бага тоо юм.

Орчуулсан: Даариймаа

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

Оролт
3 10
10 20 30
Гаралт
1
Оролт
3 4
1 2 3
Гаралт
4

Тэмдэглэл

Эхний жишээнд бид $(10, 20, 30)$ массив дээр $9$-ийн тоо нэмж болно. Үр дүнд үүссэн $(9, 10, 20, 30)$ массивын дундах байрлал нь $\lfloor\frac{4+1}{2}\rfloor$ буюу $10$ утга байна.

Хоёр дахь жишээнд та ($4$, $5$, $5$, $5$) тоонуудыг нэмж болно. Үр дүнд үүссэн массивын дундах утга нь $4$-тэй тэнцүү.

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