Problem: The array a with n integers is given. Let's call the sequence of one or more consecutive elements in a segment. Also let's call the segment k-good if it contains no more than k different values.

Find any longest k-good segment.

As the input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

Input

The first line contains two integers n, k (1 ≤ k ≤ n ≤ 5·105) — the number of elements in a and the parameter k.

The second line contains n integers ai (0 ≤ ai ≤ 106) — the elements of the array a.

Output

Print two integers l, r (1 ≤ l ≤ r ≤ n) — the index of the left and the index of the right ends of some k-good longest segment. If there are several longest segments you can print any of them. The elements in a are numbered from 1 to n from left to right.

Examples

Input

5 5
1 2 3 4 5


Output

1 5


Input

9 3
6 5 1 2 3 2 1 4 5


Output

3 7


Input

3 1
1 2 3


Output

1 1

Solution (in PYTHON3):

Solution:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2016 missingdays <missingdays@missingdays>
#
# Distributed under terms of the MIT license.

"""

"""

def good(nums):
    for num in nums:
        if nums[num] > 1:
            return True
    return False

n = int(input())

a = [int(i) for i in input().split()]

s = []

l, r = 0, 0
nums = {}

for i in range(n):
    num = a[i]

    if num in nums:
        break
    else:
        nums[num] = True
else:
    print(-1)
    exit()

nums = {}

while r < n:
    while r < n:
        num = a[r]

        if num in nums:
            r += 1
            break
        else:
            nums[num] = True

        r += 1

    r -= 1

    s.append([l, r])
    r += 1
    l = r

    nums = {}

length = len(s)

last = s[length-1]

for i in range(last[0], last[1]+1):
    num = a[i]
    if num in nums:
        print(length)
        break
    else:
        nums[num] = True
else:
    s.pop()

    s[length-2][1] = n-1

    print(length-1)

for st in s:
    for c in st:
        print(c+1, end=" ")
    print()