题目描述

Farmer John 雇了一位摄影师为他的奶牛拍合照。
牛棚里共有 N 头奶牛 排成一条直线，每头奶牛有两个属性：

• x：该奶牛在直线上的坐标（整数，不保证递增）；
• id：该奶牛的品种编号（整数，不同品种互不相同）。

FJ 要求合影至少包含每个不同品种的一头奶牛。
摄影师只能给连续的一段区间拍照。
拍照的成本定义为：区间中最大 x 与最小 x 的差值。

请你帮 FJ 找出满足条件的最小成本。

输入格式

• 第 1 行：一个整数 N（1 ≤ N ≤ 50 000），奶牛总数。
• 接下来 N 行：每行两个空格分隔的整数 x id（1 ≤ x, id ≤ 1 000 000 000），分别表示该奶牛的坐标和品种编号。

输出格式

• 第 1 行：一个整数，满足条件的最小拍照成本（即区间长度最小值）。

样例

样例输入

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

样例输出

4

数据范围与提示

• 1 ≤ N ≤ 50 000
• 1 ≤ x, id ≤ 1 000 000 000
• 保证不同品种互不相同
• 坐标不保证有序