题目描述

在一条笔直的街道上分布着N个珠宝店，每个珠宝店都只出售一种类型的宝石。其中第i家店的位置为xi，出售的珠宝种类为di。小H计划拍选择一段位置紧邻的珠宝店，使得这些珠宝店出售的珠宝种类包含了这条街的全部种类，并且要求这一段珠宝店距离最小，即该段中珠宝店最大位置和最小位置之差。

请帮助小H计算这个最小距离。

输入格式

• 第 \(1\) 行：奶牛的数量 \(N\)（\(1 \leq N \leq 50,000\)）。
• 第 \(2\) 行到第 \(1+N\) 行：每行包含两个用空格分隔的正整数，分别表示一家珠宝店的 \(xi\) 坐标和出售珠宝的种类di。这两个数字的最大值为 \(10^9\)。

输出格式

• 输出一个整数，表示最小距离。

输入输出样例 #1

输入 #1

6 
25 7 
26 1 
15 1 
22 3 
20 1 
30 1 

输出 #1

4 

说明/提示

有 \(6\) 家珠宝店，位置分别为 \(25\)、\(26\)、\(15\)、\(22\)、\(20\)、\(30\)，出售珠宝的种类分别为 \(7\)、\(1\)、\(1\)、\(3\)、\(1\)、\(1\)。

从 \(x=22\) 到 \(x=26\) 的范围（总大小为 \(4\)）包含了每种不同的品种的珠宝：\(1\)、\(3\) 和 \(7\)。