A well-organised 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
To move a dumbbell, you may either roll it to a free
neighbouring space on the same row with almost no effort, or
you may pick 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.
The input consists of:
one line containing the integer $n$ ($1 \le n \le 10^6$), the number of
two lines, each containing $n$ integers $w_1 \ldots w_ n$ ($1 \le w_ i \le 10^9$ for each
$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 the weight of the heaviest dumbbell that must be
moved, in order that all items can be paired up while lifting
the smallest possible maximum weight.
|Sample Input 1
||Sample Output 1
2 1 8 2 8
9 9 4 1 4
|Sample Input 2
||Sample Output 2
7 7 15 15 2 2 4 4
5 5 3 3 9 9 1 1