33703번 - 건덕이의 돌탑

문제

아래는 건덕이의 돌탑에 대한 설명이다.

• 방석 3ドル$개가 있고 첫 번째 방석 위에 크기가 서로 다른 $N$개의 돌이 일렬로 쌓여있다. 돌의 크기가 클수록 아래에 쌓여있다.
• 한 방석에 있는 돌 한 개를 빼서 다른 방석으로 옮길 수 있다. 건덕이는 뺀 돌을 돌이 없는 방석이나 크기가 더 큰 돌 위로만 옮길 수 있다.
• 돌을 옮긴 후, 각 방석 위의 돌은 일렬로 돌의 크기가 클수록 아래에 쌓여있어야 한다.

건덕이는 다음과 같은 방식으로 돌을 뺄 수 있다.

• 건덕이는 방석 위에 돌이 1ドル$개만 있다면 해당 돌을 뺄 수 있다.
• 돌이 2ドル$개 이상인 경우, 건덕이는 중간에 있는 돌도 잘 빼기 때문에 빼려는 돌이 맨 밑만 아니라면 뺄 수 있다.

건덕이는 모든 돌을 세 번째 방석으로 옮기고 싶어 한다. 이때 필요한 돌의 최소 이동 횟수를 구해보자.

입력

첫 번째 방석 위에 쌓여있는 돌의 개수 $N$이 주어진다. $\left(1 \le N \le 100,円 000\right)$

출력

모든 돌을 세 번째 방석으로 옮기는 데 필요한 돌의 최소 이동 횟수를 출력한다.

제한

노트

정답이 매우 커질 수 있음에 유의해 주세요. C/C++에서는 int 대신 long long을, Java에서는 long 자료형을 사용하는 것을 권장합니다. Python은 기본적으로 큰 수를 지원하므로 정수 자료형을 고려할 필요가 없습니다.