Busy Beaver와 Busy Revaeb의 세기를 다투는 경쟁은 오늘날까지도 계속되고 있습니다. 이번에 그들은 2인용 게임으로 서로에게 도전하기로 했습니다.

$N$개의 양의 정수로 이루어진 수열 $a_1, \dots, a_N$이 있습니다. Busy Beaver와 Busy Revaeb은 다음과 같은 턴제 게임을 진행합니다.

• Busy Beaver는 수열에서 인접한 두 수를 선택하여 지우고, 지운 두 수 중 더 큰 수를 적습니다.
• Busy Revaeb은 같은 방식으로 진행하되, 지운 두 수 중 더 작은 수를 적습니다.

Busy Beaver가 먼저 시작합니다. 수열에 단 하나의 수 $X$만 남으면 게임이 종료됩니다. Busy Beaver는 $X$를 최대화하려고 하고, Busy Revaeb은 $X$를 최소화하려고 합니다. 두 플레이어가 최적으로 플레이할 때 $X$의 값을 구하십시오.

입력

첫 번째 줄에는 배열의 원소 개수인 $N$ ($1 \leq N \leq 2 \cdot 10^5$)이 주어집니다.

두 번째 줄에는 $N$개의 정수 $a_1, \dots, a_N$ ($1 \le a_i \le 10^9$)이 공백으로 구분되어 주어집니다.

출력

두 플레이어가 최적으로 플레이했을 때 마지막에 남는 하나의 원소 값을 출력하십시오.

예제

입력 1

3
2 1 4

출력 1

2

참고 1

마지막 값은 $4$가 될 수 없습니다. Busy Beaver가 첫 번째 라운드에서 $4$를 선택하지 않음으로써 $4$를 유지하려고 해도, Busy Revaeb이 다음 라운드에서 $4$를 가져가 버리면 마지막 값은 $1$이나 $2$가 되기 때문입니다. 마지막 값은 $1$이 될 수도 없습니다. Busy Revaeb이 첫 번째 라운드에서 $1$을 가져가면 마지막 값이 $1$보다 크게 만들 수 있기 때문입니다.

Busy Beaver는 마지막 값이 최소 $2$가 되도록 할 수 있고, Busy Revaeb은 마지막 값이 최대 $2$가 되도록 할 수 있습니다. 따라서 최적의 플레이 하에서 마지막 값은 $2$가 됩니다.

입력 2

4
1 1 1 2

출력 2

1

참고 2

마지막 값은 $1$ 또는 $2$입니다. Busy Revaeb의 전략이 $2$를 가능한 한 빨리 가져가는 것이라면, Busy Beaver가 첫 번째 턴에 어떻게 움직이든 상관없이 자신의 턴(두 번째 턴)이 끝난 후 수열에 $1$만 남도록 보장할 수 있습니다. 따라서 두 플레이어가 최적으로 플레이하면 마지막 값은 $1$이 됩니다.

서브태스크

• ($15$점) $N \leq 3$.
• ($25$점) $1 \leq a_i \leq 2$.
• ($60$점) 추가 제약 조건 없음.