题目描述

农民约翰雇佣了一位专业摄影师来拍摄他的一些奶牛。由于约翰的奶牛代表了多种不同的品种，他希望照片中至少包含他牛群中每种不同品种的一头奶牛。

约翰的 $N$ 头奶牛都站在一条线上的不同位置，每头奶牛的位置由一个整数（即其 $x$ 坐标）和一个整数品种 ID 描述。约翰计划拍摄一段连续的奶牛范围。该照片的成本等于其大小——即照片中奶牛的最大和最小 $x$ 坐标之间的差。

请帮助约翰计算出一张照片的最小成本，其中至少包含约翰牛群中每种不同品种的一头奶牛。

输入格式

• 第 $1$ 行：奶牛的数量 $N$（$1 \leq N \leq 50,000$）。
• 第 $2$ 行到第 $1+N$ 行：每行包含两个用空格分隔的正整数，分别指定一头奶牛的 $x$ 坐标和品种 ID。这两个数字的最大值为 $10^9$。

输出格式

• 第 $1$ 行：包含每种不同品种 ID 的照片的最小成本。

输入输出样例 #1

输入 #1

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

输出 #1

4 

说明/提示

有 $6$ 头奶牛，位置分别为 $25$、$26$、$15$、$22$、$20$、$30$，品种 ID 分别为 $7$、$1$、$1$、$3$、$1$、$1$。

从 $x=22$ 到 $x=26$ 的范围（总大小为 $4$）包含了约翰的牛群中每种不同的品种 ID：$1$、$3$ 和 $7$。