Задача G. (20081222) Комната

Автор:Пётр Митричев (идея), Александр Калужин (текст)   Ограничение времени:2 сек
Входной файл:room.in   Ограничение памяти:64 Мб
Выходной файл:room.out  
Максимальный балл:100  

Условие

В комнате находятся N рядов стульев. На них необходимо усадить девочек и мальчиков следующим образом: в первом ряду должно располагаться ровно N человек, во втором — N − 1 человек, \dots, в N-м ряду будет один человек. То есть:

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

Ваша задача — для заданного N вычислить максимальное возможное количество мальчиков при таких ограничениях.

Формат входного файла

В первой и единственной строке входного файла находится единственное натуральное число N (1 ≤ N ≤ 10101).

Формат выходного файла

Выходной файл должен содержать единственное число без ведущих нулей — ответ на поставленную задачу.

Примеры тестов

Входной файл (room.in) Выходной файл (room.out)
1
5
10
2
13
61

0.098s 0.011s 15