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

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 10⁹

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

1

1

3

3

15

7

Разбор

Последовательность номеров шагов, когда робот получает очко, определяется следующим образом:
a₁ = 1,
a₂ = a₁ + 1, a₃ = a₂ + 1,
a₄ = a₃ + 2, a₅ = a₄ + 2,
a₆ = a₅ + 3, a₇ = a₆ + 3,
a₈ = a₇ + 4, a₉ = a₈ + 4,
a₁₀ = a₉ + 5, a₁₁ = a₁₀ + 5
и так далее.

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