P1638 逛画展
题目描述
博览馆正在展出由世上最佳的 m 位画家所画的 n 幅图画,这些图画按 1∼n 的顺序依次排列。
游客在购买门票时必须说明两个整数 x 和 y,代表他要看展览中的第 x 幅画至第 y 幅画(包含第 x 幅与第 y 幅)之间的所有图画。门票的价钱等于他观看的图画数量,而一张图画一元。
Sept 希望入场后可以看到所有名师的图画,并且想最小化购买门票的价格。
请求出他购买门票时应选择的 x,y,数据保证一定有解。
若存在多组解,输出 x 最小的那组。
输入格式
第一行输入两个整数 $n,m \left(1 \leqq n \leqq 10^6;\ 1 \leqq m \leqq 2 \times 10^3\right)$,分别代表博览馆内的图画总数,以及这些图画是由多少位名师所绘画的。
第二行输入 n 个整数 a1,a2,…,an(1≦ai≦m),其中 ai 代表画第 i 幅画的名师的编号。
输出格式
在一行上输出两个整数 x,y(1≦x≦y≦n),代表他购买门票时应选择的两个数字。
测试样例
12 5
2 5 3 1 3 2 4 1 1 5 4 3
2 7
样例 1 解释
在这个样例中,选择 x=2,y=7 时,可以看到第 2 幅至第 7 幅画,对应名师的编号为 5,3,1,3,2,4,包含全部 5 位名师的图画,门票价格为 6。
不存在长度小于 6 的可行区间,因此最小的门票价格为 6;而在长度为 6 的可行区间中还有 x=5,y=10 这一组,它的 x 更大,所以输出 x 最小的 x=2,y=7。
数据范围与提示
对于 30% 的数据,n≦200,m≦20;
对于 60% 的数据,n≦105,m≦103;
对于 100% 的数据,1≦n≦106,1≦ai≦m≦2×103。