방벽 게임

건덕이와 건구스는 $N$행 $2$열의 칸으로 이루어진 전장에서 승부를 겨루고 있다. 건덕이는 $1$행 $1$열에서 출발하여 말을 $N$행까지 옮겨야 한다. 건구스는 칸과 칸 사이에 방벽을 설치해 건덕이를 저지할 수 있다.

게임은 건덕이의 말이 $N$행에 도달할 때까지 아래 순서로 반복된다.

• 건덕이가 말을 상하좌우로 인접한 칸으로 옮긴다. 단, 현재 칸과 이동하려는 칸 사이에 방벽이 있으면 그 칸으로 갈 수 없다.
• 건구스가 게임판 안에서 가로 또는 세로로 연속한 두 칸을 골라 그 사이에 방벽을 설치한다. 단, 건덕이가 $N$행에 도달할 수 없도록 막아서는 안 된다. 조건에 맞게 방벽을 설치할 수 없거나 설치하고 싶지 않으면 차례를 넘길 수 있다.

건덕이는 말을 최대한 빨리, 건구스는 최대한 늦게 $N$행에 도달하게 하려고 한다. 모두가 최선을 다할 때, 말이 $N$행에 도달하기 위한 이동 횟수를 구하라.

첫째 줄에 격자의 행 수 $N$이 주어진다. $\left(2 \leq N \leq 1,000,000\right)$

말이 $N$행에 도달하기 위한 이동 횟수를 출력한다.

$N = 3$일 때 풀이

초기상태	1턴 - 건덕이: 말 이동	1턴 - 건구스: 방벽 설치
2턴 - 건덕이: 말 이동	2턴 - 건구스: 방벽 설치	3턴 - 건덕이: 말 이동 후 도착

건덕이와 건구스가 최선으로 게임할 때 말이 $3$턴 후 $N$행에 도착하게 된다.