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

Лестница состоит из n ступенек. Ступеньки пронумерованы снизу вверх (то есть 1-я — самая нижняя, а n-я — самая верхняя). Над каждой ступенькой висит стрелка, указывающая направление движения (вверх или вниз) с этой ступеньки, причем, как только Оля уходит с очередной ступеньки, направление стрелки над ней меняется на противоположное, то есть направление «вверх» меняется на направление «вниз», а направление «вниз» — на направление «вверх».

Оля всегда перемещается на следующую ступеньку в том направлении, что указано на текущей ступеньке.

Если Оля выйдет за пределы лестницы, то она упадёт и проснётся. Выходом за пределы лестницы считается движение вниз с первой ступеньки или движение вверх с последней (то есть n-й) ступеньки.

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

Для каждой ступеньки посчитайте длительность сна, если Оля оказывается на этой ступеньке в самом начале сна.

Падение Оли занимает тоже одну секунду, то есть, если она оказалась на первой ступеньке и идёт вниз, то она проснётся в следующую секунду.