32518번 - 대충 블록에서 영혼 탈출시키는 게임

문제

어느 날 대구과학고등학교에 악마가 나타나 $N$개의 블록에 학생들의 영혼을 하나씩 가두었다. $N$개의 블록은 일렬로 나열되어 있으며, 인접한 블록은 사슬로 이어져 있다. 어떤 블록에서 출발하여 사슬로 이어진 블록으로 이동하는 과정을 반복하여 이동할 수 있는 블록의 집합을 체인이라고 하고, 체인을 이루는 블록의 개수를 체인의 길이라고 한다. 따라서 처음에는 모든 $N$개의 블록이 하나의 체인을 이루며 그 체인의 길이는 $N$이다.

이안이는 길이가 3ドル$ 이상인 체인이 없을 때까지 아래와 같은 과정을 반복하여 블록을 들어내서 영혼을 탈출시키려고 한다. 블록을 들어내면 그 블록에 직접 이어져 있던 사슬은 모두 제거된다.

• 길이가 3ドル$ 이상인 체인 $C$를 고른다.
• $C$의 길이가 4ドル$ 이하인 경우 하나의 블록을 들어내고, 그렇지 않은 경우 인접하지 않은 두 개의 블록을 들어낸다. 블록을 들어낼 때는 다음의 조건을 만족해야 한다.
  • 들어내는 블록에는 사슬 두 개가 인접해 있어야 한다. 즉, 체인의 양 끝점에 있는 블록을 들어내서는 안 된다.
  • 블록을 들어내면 $C$는 더 이상 체인이 아니게 되며, 2ドル$개 또는 3ドル$개의 새로운 체인이 만들어진다. 새로 만들어진 체인 중 길이의 최솟값은 가능한 한 커야 한다.

양적 공리주의를 옹호하는 이안이는, 위의 과정을 반복하여 최대한 많은 영혼을 탈출시키려고 한다. 이안이가 들어낼 수 있는 블록의 개수의 최댓값을 구하여라.

입력

첫 번째 줄에 블록의 개수 $N$이 주어진다.

출력

이안이가 들어낼 수 있는 블록 개수의 최댓값을 하나의 정수로 출력한다.

제한

• $N$은 1ドル \le N \le 10^{18}$을 만족하는 정수이다.

힌트