Задача A. Робот, налево!

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

В Центре робототехники изобрели робота, который ходит только налево. На вопрос "зачем?" он затрудняется ответить.

Робот занимает одну клеточку и действует по следующему алгоритму.

  1. Развернуться влево.
  2. Если следующая клеточка не была посещена ранее, то пойти прямо (1). Иначе развернуться вправо и пойти прямо (2).

За шаг вида (1) робот получает 1 очко, за шаг вида (2) — 0 очков. Сколько очков получит робот, сделав N шагов?

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

Входной файл содержит целое число N.

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

Выходной файл должен содержать число очков.

Ограничения

1 ≤ N ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1
1
2
3
3
3
15
7

Разбор

Последовательность номеров шагов, когда робот получает очко, определяется следующим образом:
a1 = 1,
a2 = a1 + 1, a3 = a2 + 1,
a4 = a3 + 2, a5 = a4 + 2,
a6 = a5 + 3, a7 = a6 + 3,
a8 = a7 + 4, a9 = a8 + 4,
a10 = a9 + 5, a11 = a10 + 5
и так далее.

Ограничения N ≤ 109 и квадратичный рост последовательности aj позволяют легко найти для заданного N максимальный номер k, для которого ak ≤ N. Это и есть ответ.


0.470s 0.162s 15