Module: two pointers


Problem

9 /11


Beauty Above All

Problem

In the park of the city of Pittsburgh there is a wonderful alley consisting of N trees planted in one row, each of one of K varieties. With Pittsburgh hosting the Byteland Open Programming Championship, it was decided to build a huge arena to host the competition. So, according to this plan, the entire alley was to be cut down. However, the Ministry of Trees and Bushes opposed this decision and demanded that some of the trees be left alone. According to the new construction plan, all trees that will not be cut down should form one continuous segment, which is a sub-segment of the original one. Each of the K tree species needs to be preserved at least one copy. Your task is to find the segment of the smallest length that satisfies the specified restrictions.
 
Input
The first line of the input file contains two numbers N and K ( 1 ≤ N , K ≤ 250000 ). The second line of the input file contains N numbers (separated by spaces), the i -th number of the second line specifies the color of the i -th tree from the left in the alley. It is guaranteed that at least one tree of each color is present
 
Output
In the output file print two numbers, the coordinates of the left and right ends of the segment of the minimum length that satisfies the condition. If there are several optimal answers, print any one.
 
Input Output
5 3
1 2 1 3 2
2 4
6 4
2 4 2 3 3 1
2 6