题目描述

农民约翰雇了一位专业摄影师给他的部分牛拍照。约翰的牛有很多品种，他希望照片中每个品种的牛至少都有一头。

约翰的牛站在一条直线上，每头牛的位置互不相同。每头牛用一个整数位置 $X_i$ 和一个整数品种编号 $ID_i$ 表示。

约翰想拍一张照片，照片将包含直线上一个连续区间内的所有牛。照片的成本等于区间内最左边牛与最右边牛的位置差（即 $X_{\max} - X_{\min}$）。换言之，成本取决于区间两端牛的距离。

请你帮助约翰计算最小的照片成本，使得照片中包含每个不同品种的至少一头牛。

输入格式

第一行：一个整数 $N$，表示牛的数量。

接下来 $N$ 行：每行两个以空格分隔的正整数 $X_i$ 和 $ID_i$，分别表示第 $i$ 头牛的位置和品种编号。

所有 $X_i$ 互不相同。

输出格式

一行一个整数，表示包含所有不同品种的最小照片成本（即最小区间长度）。

样例

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

4

样例解释

共有三种品种：1、3、7。

选择区间 $[22, 26]$ 中包含的三头牛：

• 位置 25，品种 7
• 位置 26，品种 1
• 位置 22，品种 3

该区间包含了所有品种，区间长度为 $26 - 22 = 4$，可以证明这是最小成本。

数据范围

• $1 \le N \le 50000$
• $1 \le X_i, ID_i \le 10^9$，所有 $X_i$ 互不相同。