32688번 - N-가위바위보

문제

게임 매니아 도훈이는 가위바위보 게임을 재밌게 만드는 방법을 고민하던 중, N-가위바위보 라는 새로운 종류의 게임을 개발했다! N-가위바위보 게임의 규칙은 다음과 같다.

• $N+1$명의 플레이어는 모두 1ドル$부터 $N$까지 적혀 있는 카드를 한 장씩 가지고 게임을 시작한다.
• 각 플레이어는 $N$명의 사람들과 각자 한 번씩 총 $N$회 대결을 진행하며, 각 대결에서 두 플레이어는 가지고 있는 카드 중 하나를 낸다.
• 두 명의 플레이어가 각각 $i$번 카드와 $i+1$번 카드를 내면 $i$번 카드를 낸 플레이어가 승리하며, $i+1$번 카드를 낸 플레이어는 패배한다. $(1\le i\le N-1)$
• 두 명의 플레이어가 각각 $N$번 카드와 1ドル$번 카드를 내면 $N$번 카드를 낸 플레이어가 승리하며, 1ドル$번 카드를 낸 플레이어는 패배한다.
• 그 외의 모든 대진은 무승부 처리가 된다.
• 각 대결의 승패 또는 무승부가 결정되면, 낸 카드는 버리고 남은 카드로만 다음 플레이어와 대결을 진행한다.

게임의 규칙을 만들어낸 도훈이는, 다음 $N$번의 대결 동안 상대방이 낼 카드의 목록을 알고 있을 때 무승부 횟수의 최댓값을 알고 싶어졌다! 도훈이를 위해 이를 구해주자.

입력

첫째 줄에 대결을 진행하는 횟수 $N$이 주어진다. $(3\le N\le 200,000円)$

둘째 줄에 다음 $N$번의 대결 중 상대방이 낼 카드의 번호 $A_1, A_2, \cdots, A_N$이 순서대로 공백으로 구분되어 주어진다. $(1 \le A_i \le N)$

출력

$N$개의 카드를 적절히 냈을 때, 무승부 횟수의 최댓값을 출력한다.

제한

힌트