/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
1 から N までの番号が付けられた N 個のおもちゃと、1 から N-1 までの番号が付けられた N-1 個の箱があります。 おもちゃ i\ (1\leq i\leq N) の大きさは A_i、箱 i\ (1\leq i\leq N-1) の大きさは B_i です。
すべてのおもちゃを別々の箱にしまいたいと考えている高橋君は、今から以下の操作を順に行うことにしました。
- 任意の正整数 x を選んで、大きさ x の箱を 1 つ購入する。
- N 個のおもちゃそれぞれを、（元々あった箱と新しく購入した箱を合わせた）N 個の箱のいずれかに入れる。 ただし、各おもちゃはそのおもちゃの大きさ以上の大きさを持つ箱にしか入れることはできず、また 1 つの箱に 2 つ以上のおもちゃを入れることもできない。
高橋君は、操作 1 で十分な大きさの箱を購入することで操作 2 が実行できるようにしたいですが、大きな箱ほど値段が高いため、可能な限り小さな箱を購入したいです。
高橋君が操作 2 を実行できるような x の値が存在するか判定し、存在するならばその最小値を求めてください。
制約
- 2\leq N \leq 2\times 10^5
- 1\leq A_i,B_i \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_{N-1}
出力
高橋君が操作 2 を実行できるような x の値が存在するならばその最小値を、存在しないならば -1 を出力せよ。
入力例 1
4 5 2 3 7 6 2 8
出力例 1
3
x=3 とした場合（すなわち、操作 1 で大きさ 3 の箱を購入した場合）を考えます。
新しく購入した箱を箱 4 と呼ぶことにすると、おもちゃ 1,\dots,4 の大きさはそれぞれ 5,2,3,7、箱 1,\dots,4 の大きさはそれぞれ 6,2,8,3 となります。 よって、おもちゃ 1 を箱 1 に、おもちゃ 2 を箱 2 に、おもちゃ 3 を箱 4 に、おもちゃ 4 を箱 3 にそれぞれ入れることができます。
逆に、x\leq 2 のときは N 個のおもちゃすべてを別々の箱に入れることができません。 よって答えは 3 です。
入力例 2
4 3 7 2 5 8 1 6
出力例 2
-1
操作 1 でどのような大きさの箱を購入したとしても、箱 2 に入れられる大きさのおもちゃが存在しないため、操作 2 を実行することができません。
入力例 3
8 2 28 17 39 57 56 37 32 34 27 73 28 76 61 27
出力例 3
37
Score : 350 points
Problem Statement
There are N toys numbered from 1 to N, and N-1 boxes numbered from 1 to N-1. Toy i\ (1 \leq i \leq N) has a size of A_i, and box i\ (1 \leq i \leq N-1) has a size of B_i.
Takahashi wants to store all the toys in separate boxes, and he has decided to perform the following steps in order:
- Choose an arbitrary positive integer x and purchase one box of size x.
- Place each of the N toys into one of the N boxes (the N-1 existing boxes plus the newly purchased box). Here, each toy can only be placed in a box whose size is not less than the toy's size, and no box can contain two or more toys.
He wants to execute step 2 by purchasing a sufficiently large box in step 1, but larger boxes are more expensive, so he wants to purchase the smallest possible box.
Determine whether there exists a value of x such that he can execute step 2, and if it exists, find the minimum such x.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_{N-1}
Output
If there exists a value of x such that Takahashi can execute step 2, print the minimum such x. Otherwise, print -1.
Sample Input 1
4 5 2 3 7 6 2 8
Sample Output 1
3
Consider the case where x=3 (that is, he purchases a box of size 3 in step 1).
If the newly purchased box is called box 4, toys 1,\dots,4 have sizes of 5, 2, 3, and 7, respectively, and boxes 1,\dots,4 have sizes of 6, 2, 8, and 3, respectively. Thus, toy 1 can be placed in box 1, toy 2 in box 2, toy 3 in box 4, and toy 4 in box 3.
On the other hand, if x \leq 2, it is impossible to place all N toys into separate boxes. Therefore, the answer is 3.
Sample Input 2
4 3 7 2 5 8 1 6
Sample Output 2
-1
No matter what size of box is purchased in step 1, no toy can be placed in box 2, so it is impossible to execute step 2.
Sample Input 3
8 2 28 17 39 57 56 37 32 34 27 73 28 76 61 27
Sample Output 3
37