В одной очень большой и очень солидной компании в раздевалке есть вешалка для пальто. Она представляет собой n крючков, расположенных в ряд. Крючки пронумерованы натуральными числами от 1 до n слева направо.

В компании очень сложный распорядок работ у сотрудников. В начале рабочего дня все сотрудники находятся не на работе, а вешалка в раздевалке пуста. В некоторые моменты времени сотрудники приходят на работу, а в некоторые уходят.

Когда сотрудник приходит на работу, он вешает на один из свободных крючков свое пальто. Чтобы доставить своим коллегам как можно меньше неудобств, крючок, на который будет повешено пальто, выбирается следующим образом. Сначала выбирается самый длинный отрезок из подряд идущих пустых крючков. Если таких отрезков несколько, то выбирается самый правый из них. После этого пальто вешается на крючок, расположенный в середине этого отрезка. Если в отрезке четное количество крючков, то пальто вешается на правый из двух срединных крючков.

Когда сотрудник уходит с работы — он забирает свое пальто. Так как все сотрудники в компании очень уважают друг друга, никто не трогает чужие пальто.

Время от времени директору этой очень солидной компании становится скучно и он отправляет свою секретаршу посмотреть сколько пальто висят на вешалке с i-го по j-ый крючок включительно. И эту прихоть приходится всегда выполнять — иначе директор начинает злиться и у него случается нервный срыв.

Чтобы не тратить слишком много времени на перемещение от кабинета директора до раздевалки и обратно, секретарша попросила вас написать программу, эмулирующую работу раздевалки компании.