시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB120514963.636%

문제

길이가 $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 300 000)$

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

출력

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

서브태스크

번호배점제한
110

$a$는 오름차순이다.

290

추가적인 제한은 없다.

예제 입력 1

4
2 4 3 1

예제 출력 1

3

예제 입력 2

5
5 2 1 3 4

예제 출력 2

3

출처

Contest > BOJ User Contest > 피갤컵 > 제3회 피갤컵 H번

채점 및 기타 정보

  • 예제는 채점하지 않는다.