Free Weights

A well-organized rack of weights.

The city of Bath is a noted olympic training ground — bringing local, national, and even international teams to practice. However, even the finest gymnasium falls victim to the cardinal sin: weights put back in the wrong spots.

All of the pairs of dumbbells sit in no particular order on the two racks, possibly even with some of them split between rows. Initially, each row has an equal number of dumbbells, however, this being a well-funded professional gym, there is infinite space at either end of each to hold any additional weights.

To move a dumbbell, you may either roll it to a free neighboring space on the same row with almost no effort, or you may pick it up and lift it to another free spot; this takes strength proportional to its weight. For each pair of dumbbells, both have the same unique weight.

What is the heaviest of the weights that you need to be able to lift in order to put identical weights next to each other? Note that you may end up with different numbers of weights on each row after rearranging; this is fine.

Input Specification

The input consists of:

• one line containing an integer n (1 ≤ n ≤ 10⁶), the number of pairs;
• two lines, each containing n integers w₁, …, w_n (1 ≤ w_i ≤ 10⁹ for each i), where w_i is the mass of the weight i-th from the left along this row.

Every weight in the input appears exactly twice.

Output Specification

Output the weight of the heaviest dumbbell that must be lifted, in order that all items can be paired up while lifting the smallest possible maximum weight.

Sample Input 1

1. 5
2. 2 1 8 2 8
3. 9 9 4 1 4

download as text file

Output for Sample Input 1

1. 2

download as text file

Sample Input 2

1. 8
2. 7 7 15 15 2 2 4 4
3. 5 5 3 3 9 9 1 1

download as text file

Output for Sample Input 2

1. 0

download as text file