Count Ones in an Infinite Binary String

Consider an infinite binary string that is formed by concatenating the binary representations of the non-negative integers in order. In other words, the string is built as follows:

$$0 \Vert 1 \Vert 10 \Vert 11 \Vert 100 \Vert 101 \Vert 110 \Vert 111 \Vert \cdots$$

The first few digits of this string are:

$$011011100101110111\dots$$

Your task is to compute the number of 1 characters among the first x digits of this infinite binary string.

inputFormat

The input consists of a single integer x (0 ≤ x ≤ 10^5 for the purposes of this problem), the number of digits to consider from the infinite binary string.

outputFormat

Output a single integer representing the number of 1s in the first x digits of the binary string.

sample

6

4