题目描述

小月要设置一列包含 $n$ 个整数的读数 $x_1,x_2,\dots,x_n$。第 $i$ 个读数必须位于给定的闭区间 $[l_i,r_i]$ 中。 这列读数需要先严格上升，再严格下降。也就是说，必须存在一个位置 $p\left(2\leqq p\leqq n-1\right)$，满足： $x_1<x_2<\dots<x_p>x_{p+1}>\dots>x_n$。 这列读数的步幅是所有相邻读数之差的绝对值的最大值，即： $\max\limits_{1\leqq i<n}|x_{i+1}-x_i|$。 请你帮小月计算在所有合法的读数设置方案中，可能的最小步幅是多少。如果无法设置满足要求的读数，输出 $-1$。官方中文

输入格式

第一行输入一个整数 $n\left(3\leqq n\leqq2\times10^5\right)$，表示读数数量。 此后 $n$ 行，第 $i$ 行输入两个整数 $l_i,r_i\left(-10^9\leqq l_i\leqq r_i\leqq10^9\right)$，表示第 $i$ 个读数的允许范围。官方中文

输出格式

如果存在符合要求的读数，输出一个整数，表示步幅的最小可能值；否则，输出 $-1$。官方中文

说明

在大部分情况下，PyPy 的运行速度优于 Python。本题我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。官方中文