J. Jupiter's Dinner
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In 2024, the Union of the Solar Planets (USP) is celebrating its 90th anniversary! To mark this occasion, Maystronauta and Astronauthan organized a dinner for the members of MaratonUSP at the best restaurant in the solar system, Red Spot, on Jupiter!

Upon arriving at the restaurant, the $$$n$$$ members of MaratonUSP sat at a single table with chairs numbered from $$$1$$$ to $$$n$$$. The person in position $$$i$$$ ordered dish number $$$a_i$$$. The renowned chefs Willian Fogaça Mori and Nathália Carosella Tsuno will take care of cooking the dishes for the evening, but the space waiter Thilio will need your help.

Like any other common Jovian, Thilio has $$$k$$$ arms. He can carry as many dishes as needed with each of his arms but with one restriction: all the dishes must be identical. For example, if everyone ordered dish 1, Thilio would be able to serve the entire table with just one arm. However, if someone ordered dish 1 and someone else ordered dish 2, he would need to carry one dish in each arm. According to the restaurant's rules, the waiter must serve a continuous range of people, i.e., choose values $$$\ell$$$ and $$$r$$$ and serve all the customers seated in the interval $$$[\ell, \dots, r]$$$.

As Thilio is a big fan of competitive programming, he would like to serve the maximum number of MaratonUSP members possible. He needs your help to find an interval $$$[\ell, \dots, r]$$$ of maximum length such that all the orders within this interval can be carried with his $$$k$$$ arms.

Input

The input consists of two lines. The first line contains two integers $$$1 \leq n, k \leq 200000$$$, where $$$n$$$ is the number of members in the group and $$$k$$$ is the number of arms of the waiter. The following line contains $$$n$$$ integers $$$1 \leq a_i \leq 200000$$$ which represent the orders of each member.

Output

The output must contain two lines. The first line is the size of a maximum interval $$$[\ell, \dots, r]$$$ with at most $$$k$$$ distinct orders inside this interval. The second line must contain two integers $$$\ell, r$$$ representing the start and the end of the interval. If there are multiple valid answers, any of them will be accepted.

Examples
Input
5 2
1 2 3 2 1
Output
3
2 4
Input
8 3
4 1 2 3 3 2 1 4
Output
6
2 7
Input
10 1
1 2 2 1 2 1 2 2 1 1
Output
2
2 3
Note

In the second test case, the interval [2,7] contains only dishes 1, 2, and 3, and therefore Thilio would be able to carry them. Note that any interval of size 7 or larger would have 4 distinct dishes, and Thilio would not be able to carry them with his 3 arms.

In the third test case, other possible answers would be the interval [7, 8] or the interval [9, 10]. Note that there is no interval of size 3 or more with all dishes of the same type.