LG#P1638. 逛画展

逛画展

P1638 逛画展

题目描述

\hspace{15pt}博览馆正在展出由世上最佳的 mm 位画家所画的 nn 幅图画,这些图画按 1∼n1 \sim n 的顺序依次排列。

\hspace{15pt}游客在购买门票时必须说明两个整数 xx 和 yy,代表他要看展览中的第 xx 幅画至第 yy 幅画(包含第 xx 幅与第 yy 幅)之间的所有图画。门票的价钱等于他观看的图画数量,而一张图画一元。

\hspace{15pt}Sept 希望入场后可以看到所有名师的图画,并且想最小化购买门票的价格。

\hspace{15pt}请求出他购买门票时应选择的 x,yx,y,数据保证一定有解。

\hspace{15pt}若存在多组解,输出 xx 最小的那组。

输入格式

\hspace{15pt}第一行输入两个整数 $n,m \left(1 \leqq n \leqq 10^6;\ 1 \leqq m \leqq 2 \times 10^3\right)$,分别代表博览馆内的图画总数,以及这些图画是由多少位名师所绘画的。

\hspace{15pt}第二行输入 nn 个整数 a1,a2,…,an(1≦ai≦m)a_1,a_2,\dots,a_n \left(1 \leqq a_i \leqq m\right),其中 aia_i 代表画第 ii 幅画的名师的编号。

输出格式

\hspace{15pt}在一行上输出两个整数 x,y(1≦x≦y≦n)x,y \left(1 \leqq x \leqq y \leqq n\right),代表他购买门票时应选择的两个数字。

测试样例

12 5
2 5 3 1 3 2 4 1 1 5 4 3

2 7

样例 1 解释

\hspace{15pt}在这个样例中,选择 x=2,y=7x=2,y=7 时,可以看到第 22 幅至第 77 幅画,对应名师的编号为 5,3,1,3,2,45,3,1,3,2,4,包含全部 55 位名师的图画,门票价格为 66。

\hspace{15pt}不存在长度小于 66 的可行区间,因此最小的门票价格为 66;而在长度为 66 的可行区间中还有 x=5,y=10x=5,y=10 这一组,它的 xx 更大,所以输出 xx 最小的 x=2,y=7x=2,y=7。

数据范围与提示

\hspace{15pt}对于 30%30\% 的数据,n≦200n \leqq 200,m≦20m \leqq 20;

\hspace{15pt}对于 60%60\% 的数据,n≦105n \leqq 10^5,m≦103m \leqq 10^3;

\hspace{15pt}对于 100%100\% 的数据,1≦n≦1061 \leqq n \leqq 10^6,1≦ai≦m≦2×1031 \leqq a_i \leqq m \leqq 2 \times 10^3。