Вы играете в игру, в которой вашему персонажу нужно преодолевать различные препятствия. Например, сейчас вам нужно спуститься с утеса. Высота утеса равна \(h\), и на каждой целой высоте \(x\) от \(1\) до \(h\) есть выдвижная платформа.
Каждая платформа либо спрятана в утесе, либо выдвинута. Изначально выдвинуто \(n\) платформ на высотах \(p_1, p_2, \dots, p_n\). Платформа на высоте \(h\) выдвинута (и на ней изначально стоит персонаж).
Если ваш персонаж стоит на выдвинутой платформе на высоте \(x\), то он может нажать на специальный рычаг, который меняет положение двух платформ: на высотах \(x\) и \(x - 1\). Другими словами, платформа, на которой вы стоите, спрячется в утес, а платформа ниже поменяет свое состояние: если она была выдвинута, она спрячется, а если она была спрятана — выдвинется. Во втором случае вы безопасно приземлитесь на нее. Заметьте, что нажать на рычаг — это единственный способ спуститься с платформы.
Ваш персонаж довольно хрупок, так что он может безопасно падать с высоты не более \(2\). Другими словами, падение с платформы \(x\) на платформу \(x - 2\) безопасно, но падение с платформы \(x\) на платформу \(x - 3\) (или ниже) смертельно.
Иногда невозможно безопасно спуститься с утеса, но вы всегда можете купить (естественно за реальные деньги) несколько магических кристаллов. Каждый магический кристалл может быть использован для изменения состояния любой платформы (за исключением платформ на высоте \(h\)). После использования кристалл исчезает.
Какое минимальное количество кристаллов вам нужно купить для того, чтобы безопасно спуститься на землю, которая находится на высоте \(0\)?