4938：[USACO11NOV] Cow Lineup S
文件提交：无需freopen
内存限制：125 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
提交：0
解决：0
题目描述
# [USACO11NOV] 奶牛排队 S
## 题目描述
农夫约翰请了一位专业摄影师，准备给他的部分奶牛拍一张照片。
由于约翰的奶牛分属多个不同品种，他希望照片里**每种出现过的品种都至少有一头奶牛入镜**。
约翰的 N 头奶牛都站在一条直线上的不同位置，每头奶牛都用一个整数坐标（即 x 坐标）和一个整数品种编号来表示。
约翰打算拍摄**直线上一段连续区间内的奶牛**。
拍摄的**成本**等于区间长度——也就是区间内所有奶牛的最大 x 坐标减去最小 x 坐标。
请你帮约翰计算：**能拍到所有品种奶牛的照片的最小成本**。
## 输入格式
* 第 1 行：奶牛数量 N（1 ≤ N ≤ 50,000）
* 第 2~N+1 行：每行两个用空格分隔的正整数，分别表示一头奶牛的 x 坐标和品种编号
两个数值最大都可达 10 亿
## 输出格式
* 第 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，满足要求。
标签: P3029|2011|USACO|离散化|队列|双指针 two-pointer
## 来源
P3029|[USACO11NOV] Cow Lineup S