3769. [USACO11NOV] Cow Lineup S

【题目描述】

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

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

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

【输入格式】

第 $1$ 行：奶牛的数量 $N$（$1 \leq N \leq 50,000$）。

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

【输出格式】

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

【样例输入】

6
25 7
26 1
15 1
22 3
20 1
30 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$。