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

Условие

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

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

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

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

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

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

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

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

5

10

13

61