20번 - 피돌이 vs 피붕이 2

길이가 $N$인 순열 $a$가 있다. 피돌이와 피붕이가 다음과 같은 게임을 한다. 피돌이 부터 시작해 번갈아 가며 다음을 반복한다. - 현재 턴인 플레이어가 적당한 $i$를 골라 $a$를 두 부분수열 $[a_1, a_2, \cdots, a_i]$와 $[a_{i+1}, a_{i+2}, \cdots, a_{|a|}]$로 나눈다. $(1\leq i<|a|)$ - 현재 턴이 아닌 플레이어가 두 부분수열 중 하나를 골라 그 수열을 $a$로 한다. $a$의 길이가 $1$이 됐을 때 $a_1$의 값이 게임의 점수가 된다. 피돌이는 점수를 최대화 하고싶고 피붕이는 점수를 최소화 하고싶다. 둘 모두 최적의 전략을 사용한다고 가정할 때 게임의 점수를 구해보자.

첫째 줄에 정수 $N$이 주어진다. $(1\leq N \leq 300000)$ 둘째 줄에 $N$개의 정수 $a_1, a_2, \cdots, a_N$가 공백으로 구분되어 주어진다. $N$개의 수는 $N$이하의 서로 다른 양의 정수임이 보장된다.

첫째 줄에 게임의 점수를 출력한다.