eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Гірлянда

Гірлянда

Ліміт часу 1 секунда
Ліміт використання пам'яті 122 MiB
prb77

Новорічну ялинку прикрашено гірляндою нескінченної довжини, що складається з послідовно з'єднаних лампочок. Коли гірлянду вмикають, загоряється лише перша лампочка, рахуючи від вимикача, яка горить одну секунду. Далі гірлянда починає мигати за таким правилом. Щосекунди для кожної лампочки перевіряється умова: якщо рівно одна із її сусідніх лампочок горить, то ця лампочка буде горіти на наступній секунді; інакше – не буде горіти. Перша лампочка має лише одну сусідню.

Напишіть програму, яка за номером секунди знаходить кількість лампочок гірлянди, що будуть горіти протягом цієї секунди.

Вхідні дані

Одне ціле число n (1n10^9) – номер секунди.

Вихідні дані

Вивести одне ціле число - кількість лампочок, що будуть горіти на секунді n.

Приклад

Вхідні дані #1
5
Вихідні дані #1
2
Автор Андрій Коротков
Джерело 2008 XXI Всеукраїнська олімпіада з інформатики, Львів, Квітень 5 - 11, тур 1