Masala #0563

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 o'sish tartibida 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.

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

Bitta qatorda Azimjonning eng yaxshi usul bilan tushungan tuzoqlar soni.