프리 웨이트

체육관에 랙이 두 개 있고, 랙마다 덤벨이 한 줄로 놓여 있다. 덤벨은 $n$쌍이고, 한 쌍을 이루는 두 덤벨의 무게는 서로 같다. 서로 다른 쌍의 무게는 모두 다르다. 처음에 각 줄에는 덤벨이 정확히 $n$개씩 놓여 있고 순서는 정해져 있지 않다. 한 쌍이 같은 줄에 나란히 있을 수도 있고 두 줄에 나뉘어 있을 수도 있다. 각 줄의 양쪽 끝에는 빈 자리가 얼마든지 있다.

덤벨은 두 가지 방법으로 옮긴다.

• 같은 줄에서 바로 옆의 빈 자리로 굴린다. 힘은 거의 들지 않는다.
• 들어 올려 어느 줄이든 빈 자리에 내려놓는다. 이때 덤벨의 무게에 비례하는 힘이 필요하다.

굴리기로는 다른 덤벨을 지나갈 수 없으므로, 들어 올려 빼내지 않는 한 한 줄 안의 순서는 그대로 유지된다. 양쪽 끝의 빈 자리가 무한하니 덤벨을 굴려 줄 중간 어디에나 빈 자리를 만들 수 있고, 들어 올린 덤벨은 어느 덤벨 옆에나 내려놓을 수 있다.

같은 쌍의 두 덤벨이 서로 옆에 오도록 정리하려고 한다. 정리를 마친 뒤 두 줄의 덤벨 개수는 서로 달라도 된다. 들어 올리는 덤벨의 무게 중 최댓값을 가장 작게 만들 때, 그 값을 구하라.

첫째 줄에 쌍의 개수 $n$이 주어진다 ($1 \le n \le 10^6$).

다음 두 줄에는 줄마다 정수 $n$개 $w_1, \dots, w_n$이 주어진다 ($1 \le w_i \le 10^9$). $w_i$는 그 줄에서 왼쪽으로부터 $i$번째 덤벨의 무게다.

입력에 나오는 각 무게는 정확히 두 번씩 등장한다.

들어 올리는 덤벨 중 가장 무거운 것의 무게를 가장 작게 했을 때, 그 무게를 한 줄에 출력한다. 아무 덤벨도 들어 올리지 않고 모든 쌍을 붙일 수 있으면 0을 출력한다.