分数: 600 点
问题陈述
给你正整数 x_1, \ldots, x_N 这样 x_1 < \cdots < x_N和正整数 y_1, \ldots, y_N.
考虑一个元组 (M, L_1, R_1, \ldots, L_M, R_M) 满足以下所有条件。
- M 是正整数。
- 对于每个 j \ (1\leq j\leq M), L_j 和 R_j 是整数,使得 L_j\leq R_j.
- 对于每个 i \ (1\leq i\leq N),正是 y_i 整数 j \ (1\leq j\leq M) 满足 L_j\leq x_i\leq R_j.
可以证明这样的元组总是存在的。找到最大值 \min \lbrace R_j-L_j\mid 1\leq j\leq M\rbrace 对于这样的元组。如果没有最大值,则打印 -1.
约束
- 1\leq N\leq 2\times 10^5
- 1\leq x_1 < \cdots < x_N \leq 10^9
- 1\leq y_i \leq 10^9
输入
输入由标准输入按以下格式给出:
N x_1 \cdots x_N y_1 \cdots y_N
输出
打印最大值 \min \lbrace R_j-L_j\mid 1\leq j\leq M\rbrace 对于满足条件的元组,或 -1 如果没有最大值。
示例输入 1
3 1 3 5 1 3 1
示例输出 1
2
例如,我们有 \min \lbrace R_j-L_j\mid 1\leq j\leq M\rbrace = 2 为元组 (3, 1, 4, 2, 4, 3, 5).
示例输入 2
3 1 10 100 2 3 2
示例输出 2
-1
例如,我们有 \min \lbrace R_j-L_j\mid 1\leq j\leq M\rbrace = 990 为元组 (3, -1000, 10, -1000, 1000, 10, 1000)。没有最大值 \min \lbrace R_j-L_j\mid 1\leq j\leq M\rbrace.
示例输入 3
7 10 31 47 55 68 73 90 3 7 4 6 3 4 4
示例输出 3
56