Окабэ и хакер Дару складывают коробки в стопку одну поверх другой. Всего есть n коробок, пронумерованных от 1 до n. Изначально коробок в стопке нет.

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

Поэтому Дару может иногда, когда Окабэ отвернется, переупорядочить коробки в стопке как ему захочется. Он может сделать это в любой момент между командами Окабэ, но он не может добавлять или удалять коробки в процессе переупорядочивания.

Скажите Дару, сколько минимум раз ему необходимо переупорядочивать коробки, чтобы он мог успешно выполнить все команды Окабэ. Гарантируется, что каждая коробка добавляется в стопку раньше, чем потребуется ее убрать.