끔찍한 진실

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

요약

n명의 등장인물이 있을 때, 진실을 알게 되는 사건들의 유형이 연속으로 같을 수 없다는 제약 아래 가능한 최대 에피소드 수를 구합니다.

문제

유명한 TV 프로그램 "Find Out"에는 n명의 등장인물과 단 하나의 끔찍한 진실이 있다. 이야기가 처음부터 끝까지 긴장감 있게 흘러가도록, 각본가는 매 에피소드마다 정확히 하나의 중요한 사건을 보여주기로 했다.

중요한 사건에는 세 가지 종류가 있다.

처음에는 아무도 진실을 알지 못한다. 모든 사건은 올바라야 하며, 알게 되는 사실은 그 시점에 실제로 참이어야 한다. 한 인물이 어떤 사실을 한 번 알게 되면, 같은 사실을 다시 알게 될 수는 없다.

또한 극에 생동감을 주기 위해, 각본가는 바로 직전 에피소드와 같은 종류의 중요한 사건을 연달아 보여주지 않는다.

이 이야기가 가질 수 있는 에피소드 수의 최댓값을 구하라.

입력의 첫 줄에 정수 n — 프로그램의 등장인물 수가 주어진다 (1 ≤ n ≤ 100).

프로그램이 가질 수 있는 에피소드 수의 최댓값을 정수 하나로 출력한다.