Однажды мальчик Вася оказался в лабиринте, состоящем из (n + 1) комнат, пронумерованных от 1 до (n + 1). Первоначально Вася находится в первой комнате, а чтобы выйти из лабиринта, нужно попасть в (n + 1)-ю.

Лабиринт устроен следующим образом. В каждой комнате лабиринта есть два односторонних портала. Рассмотрим комнату с номером i (1 ≤ i ≤ n), с помощью первого портала можно перейти из нее в комнату с номером (i + 1), с помощью второго можно перейти из нее в комнату с номером p_i, где 1 ≤ p_i ≤ i.

Чтобы не заблудиться Вася решил действовать следующим образом.

• Каждый раз когда Вася приходит в какую-то комнату он рисует на ее потолке крестик. Изначально, Вася рисует крестик на потолке комнаты 1.
• Пусть Вася находится в комнате i и уже нарисовал крестик на ее потолке. Тогда, если сейчас на потолке нарисовано нечетное количество крестиков, Вася будет пользоваться вторым порталом (он ведет в комнату p_i), иначе Вася будет пользоваться первым порталом.

Помогите Васе определить, сколько раз ему придется воспользоваться порталами, чтобы попасть в комнату (n + 1) в конечном итоге.