매드 맥스

서로 다른 음이 아닌 정수 $N$개로 이루어진 수열 $A$가 주어진다.

$A$의 비어 있지 않은 모든 부분수열[1] $B$에 대해서, $\mathrm{med}$[2]$(B) +\mathrm{mex}$[3]$(B)$의 최댓값을 출력하라.

1$B$가 $A$의 부분수열이라는 것은, 수열 $A$에서 $0$개 이상의 원소를 지웠을 때 수열 $B$가 될 수 있음을 의미한다. 이때, $B$가 $A$에서 연속할 필요는 없다. 예를 들어, $A=\[2,3,0,4]$라고 하면 $\[3,4]$와 $\[2,3,0,4]$는 $A$의 부분수열이지만, $\[3,2]$와 $\[2,1,4]$는 $A$의 부분수열이 아니다.

2$\mathrm{med}(X)$는 수열 $X$의 중앙값(median)으로, $X$에서 $\left( \lfloor\frac{|X|}{2}\rfloor +1 \right)$번째로 작은 원소를 의미한다. 예를 들어, $\mathrm{med}(\[5,2,6]) =5$, $\mathrm{med}(\[0,3,2,7]) =3$이다. $X$의 길이가 짝수일 때 중앙값의 통상적인 정의와 다를 수 있음에 유의하라.

3$\mathrm{mex}(X)$는 수열 $X$에 포함되지 않는 가장 작은 음이 아닌 정수(minimum excluded value)를 의미한다. 예를 들어, $\[1,2]$에는 $0$이 포함되어 있지 않으므로 $\mathrm{mex}(\[1,2]) =0$이고, $\[3,1,0,4]$에는 $0$과 $1$이 포함되어 있지만 $2$는 포함되어 있지 않으므로 $\mathrm{mex}(\[3,1,0,4]) =2$이다.

첫째 줄에 수열의 길이 $N$이 주어진다. ($2\leq N\leq 200\\, 000$)

둘째 줄에 $N$개의 정수 $A\_{1},A\_{2},\cdots ,A\_{N}$이 공백으로 구분되어 주어진다. ($0\leq A\_i\leq{10}^9$)

모든 $A\_i$의 값은 서로 다르다.

문제의 정답을 나타내는 하나의 정수를 출력한다.

$\lfloor\frac{|X|}{2}\rfloor$는 수열 $X$의 길이를 $2$로 나눈 몫과 같다.