34829번 - 매드 맥스

문제

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

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

¹$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$의 부분수열이 아니다.

²$\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$의 길이가 짝수일 때 중앙값의 통상적인 정의와 다를 수 있음에 유의하라.

³$\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ドル$로 나눈 몫과 같다.