Masala #0180

Xotira 16 MB Vaqt 1000 ms
14

Shaxmat musobaqasi

Baytlandiya mamlakatida shaxmat o’yinchilar jami 100 ta darajaga bo’lingan, 1-darajali shaxmat o’yinchisi strategik jihatdan eng kuchsiz hisoblanadi, 100-darajali shaxmat o’yinchisi esa strategik jihatdan eng kuchli hisoblanadi. Va yanam shu ma’lumki, bu mamlakatda strategik kuchli o’yinchi doim shaxmat musobaqasida strategik kuchsizroq o’yinchining ustidan g’alaba qozongan, strategiyasi tenglar esa o’yinda teng kuchli bo’lib doim during natija qayd etishgan. Bu mamlakatda shunday kitob borki, uni 1 marotaba o’qigan shaxmatchining strategiyasi 1 ga ortadi, bu kitobni bir necha marotaba o’qib chiqish mumkin, va har o’qiganda strategik darajasi 1 ga ortib boraveradi (100-darajaga yetgandan so’ng strategik daraja ortmaydi).

Megaboy xalqaro shaxmat musobaqasining saralash bosqichiga qatnashmoqchi, hozirda uning strategik darajasi k ga teng. Boshqa ishtirokchilardan farqli o’laroq Megaboy shaxmat musobaqasi tashkilotchisining o’g’li va u otasining yordamida o’z raqiblarining strategik kuchlilik darajalarini aniqlab oldi. Uning aniqlashicha musobaqa jarayonida unga jami N ta raqib to’g’ri keladi. O’yinda keyingi bosqichga faqatgina hech kimga yutqazmagan o’yinchilargina chiqa oladi. Siz Megaboy keyingi bosqichga o’ta olishi uchun shaxmatchilar kitobini eng kamida necha marotaba o’qib chiqishi kerakligini aniqlang.


Kiruvchi ma'lumotlar:

Dastlabki satrda ikkita butun son, N(1 ≤ N ≤ 100) va K sonlari kiritiladi. Keyingi qatorda N ta butun son, Megaboyning raqiblarining strategik darajalari kiritiladi.


Chiquvchi ma'lumotlar:

Megaboy keyingi bosqichga o’ta olishi uchun shaxmatchilar kitobini eng kamida necha marotaba o’qib chiqishi kerakligini aniqlang.


Misollar
# input.txt output.txt
1
5 4
1 6 3 5 2
2