#CTR0003. 江月诗的书籍选取

    ID: 291 传统题 1000ms 256MiB 尝试: 11 已通过: 5 难度: 10 上传者: 标签>搜索搜索与剪枝其他离散化训练赛枚举优化双指针

江月诗的书籍选取

题目描述

江月诗计划去图书馆借书。图书馆的书架上有许多书,每本书都有一个唯一的编号和所属的类别(如文学、历史、科学等)。为了满足他的需求,他希望借阅的书籍至少涵盖所有不同类别的书籍。

他需要在书架上选择一个连续的区间,确保这个区间的书籍包含图书馆内每个类别的至少一本书。他想要找到一个区间,使得该区间的长度最小。

这个区间的长度等于该区间最小和最大书籍编号之间的差(即区间的“大小”)。

现在请你帮助江月诗计算出一个包含每种不同书籍类别的最小区间大小。

输入格式

第一行:书籍的数量 NN1N50,0001 \leq N \leq 50,000)。

接下来的 NN 行:每行包含两个用空格分隔的正整数,分别表示每本书的编号和所属的类别ID。这两个数字的最大值为 10910^9

输出格式

输出一行:包含每种不同书籍类别的最小区间大小。

样例输入

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

样例输出

4

说明/提示

【样例解释】

在这个图书馆的书架上,有 66 本书,编号分别为 252526261515222220203030,类别ID分别为 771111331111

从编号 2222 到编号 2626 的区间(总大小为 44)包含了图书馆内每种不同类别的书籍:113377。因此,这段区间的大小是最小的,且其大小为 44