题目描述

有 $N$ 个人准备拍合照。第 $i$ 个人站在数轴上的位置 $x_i$，所属小组的编号为 $id_i$。同一小组可以有多人。

摄影师要选择一段闭区间，使每个小组至少有一人位于区间内。区间的宽度为右端点坐标减去左端点坐标。

请计算满足要求的区间的最小宽度。

输入格式

第一行包含一个整数 $N$，表示人数。

接下来 $N$ 行，每行包含两个整数 $x_i,id_i$，分别表示第 $i$ 个人的位置和小组编号。

输出格式

输出一个整数，表示区间的最小宽度。

6
12 1
1 2
8 3
3 2
4 1
9 3

5

数据范围与提示

• $1 \le N \le 50000$
• $0 \le x_i \le 10^9$
• $1 \le id_i \le 10^9$