25346번 - 다오와 트리플 멕스 게임

문제

배고픈 다오는 신메뉴인 트리플 멕스 버거를 먹기 위해서 멕스날드에 갔다. 마침 멕스날드는 신메뉴를 낸 기념으로 트리플 멕스 게임에서 높은 점수를 얻으면 단품을 세트로 업그레이드 해주는 이벤트를 진행하고 있었고, 다오는 게임에 참여하기로 했다.

트리플 멕스 게임은 주어지는 길이 $N$의 배열 $A$와 빈 배열 $B, C$로 시작한다. 플레이어는 두 가지 행동을 할 수 있다.

1. 배열 A의 subsequence를 잡아 이들의 mex 값을 배열 $B$의 맨 뒤에 적는다.
2. 배열 B의 subarray를 잡아 이들의 mex 값을 배열 $C$의 맨 뒤에 적는다.

이때 플레이어가 얻게 될 점수는 배열 $C$에 존재하는 모든 원소들의 mex값이다. subsequence, subarray, mex의 정의는 힌트를 참고할 수 있다.

다오는 자신이 얻을 수 있는 최고 점수를 미리 계산하여 높은 점수를 얻을 수 없으면 굳이 참여하지 않으려고 한다. 다오를 도와서 다오가 주어진 배열 $A$에 대해서 얻을 수 있는 최고 점수를 계산해보자!

입력

첫째 줄에는 배열 $A$의 길이 $N$이 주어진다.

둘째 줄에는 배열 $A$의 원소 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다.

모든 입력은 정수이다.

출력

다오가 얻을 수 있는 최대 점수를 출력한다.

제한

• 1ドル \leq N \leq 100,000$
• 0ドル \leq A_{i} \leq 10^{9}$

힌트

어떤 배열의 Subsequence는 주어진 배열에서 0개 이상의 원소를 제거하여 만들어진 배열을 의미한다. 단, 이 문제에서 빈 배열은 Subsequence가 아니다.

어떤 배열의 Subarray는 주어진 배열의 연속된 부분을 의미한다. 단, 이 문제에서 빈 배열은 Subarray가 아니다.

어떤 배열의 mex는 배열에서 나타나지 않는 0 이상의 가장 작은 정수이다. 추가적인 설명은 https://en.wikipedia.org/wiki/Mex_(mathematics) 를 참조하면 된다.