Question
Clash Ring
Mira oversees M beasts arranged in a circle, each with power Bi for the ith beast. In each contest round, the two mightiest beasts battle: if their powers are equal, both perish; otherwise, the weaker dies, and its power is deducted from the stronger’s. Dead beasts are removed from the circle. Determine the power of the final surviving beast.
Input
The first line of the input contains a single integer M.
The second line of the input contains M space-separated integers.
The second line of the input contains M space-separated integers.
Output
Print the power of the final surviving beast.
Example
Sample Input
5
6 7 4 1 7
Sample Output
1
Explanation
First, the two beasts with powers 7 and 7 battle and both perish. Next, the beasts with powers 4 and 6 fight, leaving the one with power 6 reduced to power 2. Finally, the beasts with powers 2 and 1 clash, resulting in the warrior with power 2 surviving with a final power of 1.
5
6 7 4 1 7
Sample Output
1
Explanation
First, the two beasts with powers 7 and 7 battle and both perish. Next, the beasts with powers 4 and 6 fight, leaving the one with power 6 reduced to power 2. Finally, the beasts with powers 2 and 1 clash, resulting in the warrior with power 2 surviving with a final power of 1.