2x+2

시간 제한1초메모리 제한512 MB

요약

n이 10^100 미만으로 주어질 때, x와 2x+2가 동시에 들어가지 않도록 {1,...,n}의 부분집합을 최대 크기로 고른다.

문제

bobo는 $n$ 개의 정수 $1, 2, \dots, n$ 을 가지고 게임을 한다.

그는 $\{1, 2, \dots, n\}$ 의 부분집합 $S$ 를 골라서 모든 $x \in S$ 에 대해 $(2x + 2) \notin S$ 가 되도록 하려고 한다.

이때 $S$ 의 최대 크기가 궁금해졌다.

첫째 줄에 정수 $n$ 이 주어진다. ( $1 \leq n < 10^{100}$ )

최대 크기를 나타내는 정수 하나를 출력한다.