← 返回题目列表

AtCoder · arc166_d

D. 间隔计数

中文机器翻译题面 查看原题

分数: 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