2910 - 【入门】逛画展

通过次数

2

提交次数

2

Time Limit : 1 秒
Memory Limit : 128 MB

博览馆正在展出由世上最佳的 M 位大师所画的图画。周周想到博览馆去看这几位大师的作品,可是那里的博览馆有一个很奇怪的规定,就是在购买门票时必须说明两个数字 ab,代表他要看展览中的第 a 幅至第 b 幅画(包含 ab)之间的所有图画,而门票的价钱就是一张画一元。

为了看到更多大师的画,周周希望入场后可以看到所有大师的图画(至少各一张),可是他又想节省金钱。作为周周的朋友,他请你写一个程序决定他购买门票时的 a 值和 b 值。

Input

第一行是 N\ (1\le N \le 10^6)M\ (1\le M \le 2000),分别代表博览馆内的图画总数及这些图画是由多少位大师的画所绘画的。

其后的一行包含 N 个数字,它们都介于 1M 之间,代表该位大师的编号,相邻两数之间以一个空格分隔。

Output

ab,由一个空格符所隔开。保证有解,如果多解,输出 a 最小的。

Examples

Input

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

Output

2 7

Hint

用一个数组记录每个数出现的次数,枚举起点,因为终点是递增的,只需从上一次的地方开始枚举,时间复杂度 \mathcal{O}(n)