Masala #0563

Xotira 16 MB Vaqt 1000 ms
14

Azimjonning sovg'asi

Azimjon bosh qotirmalarga qiziqadi. U bir kuni akasi bilan shunday o'yin o'ynadiki o'yinda \(n\) ta uy bor, uylar 1 dan \(n\) gacha raqamlangan, bu uylarning ichida \(k\) tadan tuzoq bor. Azimjonning akasi \(A\) raqamli uyga sovg'a yashirgan. Azimjon sovg'ani olguncha eng kamida nechta tuzoqni bosib utishi kerak. Azimjon bu o'yinda optimal (eng yaxshi) o'yinchi deb hisoblansin.
Azimjonga yordam sifatida, akasi sovg`ali xonadan tashqari hamma xonaga \(>\) yoki \(<\) belgili plakat ilib chiqdi, \(>\) belgisi qidirilayotgan xona teparoqda \(<\) belgisi qidirilayotgan xona pastroqda ekanligini anglatadi.
Uy raqamlari tartiblangan holda bo'ladi. Azimjonnig uzi bu ishni uddalay olmaydi, siz Azimjonga yordam bering.


Kiruvchi ma'lumotlar:

Bitta qatorda \(n\), \(k\) va \(A\) butun sonlari. \((1 \le A \le n \le 10^{18}, 1 \le k \le 5000)\)


Chiquvchi ma'lumotlar:

Bitta qatorda Azimjonning eng yaxshi usul bilan tushungan tuzoqlar soni.


Misollar
# input.txt output.txt
1
21 5 20
20