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·10^5) — the number of elements in a and the parameter k.

The second line contains n integers a_{i} (0 ≤ a_{i} ≤ 10^6) — 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

Difficulty: interview

Starter code:

Solutions:
import sys
n, m = list(map(int, sys.stdin.readline().split()))
vis = [0] * 1000005
num = list(map(int, sys.stdin.readline().split()))
flag = 0
temp = num[0]
for i in range(n):
    if num[i] != temp:
        flag = 1
        break
if flag == 0:
    print("{0} {1}".format(1, n))
else:
    l = 0
    r = 0
    al = 0
    ar = 0
    ans = 0
    now = 0
    for i in range(n):
        vis[num[i]] += 1
        if vis[num[i]] == 1:
            now += 1
        while now > m:
            vis[num[l]] -= 1
            if vis[num[l]] == 0:
                now -= 1
            l += 1
        if i - l + 1 > ar - al + 1:
            ar = i
            al = l
    print('{0} {1}'.format(al+1, ar+1))







s1 = input().split()
length = int(s1[0])
max_k = int(s1[1])
s2 = input()

arr = s2.split()
start = 0
end = 0
dist = dict()
s = start
max_l = 0
for i in range(length):
    cur = arr[i]
    if cur not in dist:
        dist[cur] = 1
    else:
        dist[cur] += 1
    k = len(dist)
    l = i - s
    if k > max_k:
        to_remove = arr[s]
        if dist[to_remove] == 1:
            dist.pop(to_remove)
        else:
            dist[to_remove] -= 1
        l -= 1
        s += 1
    if l > max_l:
        start = s
        max_l = l
        end = i


print(start + 1, end + 1)


from collections import defaultdict

n, k = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
D = defaultdict(int)
l = 0
argmax = (0, 0)
for i in range(n):
    D[A[i]] += 1
    if len(D) > k:
        if argmax[1] - argmax[0] < i-1 - l: argmax = (l, i-1)
        while len(D) > k:
            D[A[l]] -= 1
            if D[A[l]] == 0: D.pop(A[l])
            l += 1
if argmax[1] - argmax[0] < n-1 - l: argmax = (l, n-1)
print(argmax[0] + 1, argmax[1] + 1)


def main():
    n, k = list(map(int, input().split()))
    l, cnt = list(map(int, input().split())), [0] * 1000001
    start = end = j = m = 0
    for i, x in enumerate(l):
        if not cnt[x]:
            k -= 1
        cnt[x] += 1
        if k < 0:
            x = l[j]
            cnt[x] -= 1
            if not cnt[x]:
                k += 1
            j += 1
        if m < i - j:
            m, start, end = i - j, j, i
    print(start + 1, end + 1)


def __starting_point():
    main()

__starting_point()

import sys

n,k = map(int, input().split())
hash = [0]*1000001
now = 0
a = list(map(int, input().split()))
ans = 0
l = 0

for r in range(n):
	hash[a[r]]+=1
	if hash[a[r]] == 1: now+=1
	while (now>k):
		hash[a[l]]-=1
		if (hash[a[l]]==0): now-=1
		l+=1
	if r-l+1>ans:
		al = l
		ar = r
		ans = r-l+1
print(al+1,ar+1)

import sys
import collections

n, k = list(map(int, input().split()))
a = list( map( int, sys.stdin.readline().split() ) )
ct = collections.defaultdict(int)
l, longest, numbers = 0, 0, 0
for r in range(n):
    ct[ a[r] ] += 1
    if ct[ a[r] ] == 1: numbers += 1
    while numbers > k:
        ct[ a[l] ] -= 1
        if ct[ a[l] ] == 0: numbers -= 1
        l += 1
    if r - l + 1 > longest:
        longest = r - l + 1
        ans = (l + 1, r + 1)
print('%d %d' %(ans))


n,k=list(map(int,input().split()))
lis=list(map(int,input().split()))

ins=[0 for i in range(10**6)]
ins[lis[0]]+=1
zeroes=10**6-1
mL=0
pair=[0,0]
r=0
for l in range(n):

    if l>0:
        ins[lis[l-1]]-=1
        if ins[lis[l-1]]==0:
            zeroes+=1

    while 10**6-zeroes<=k and r<n-1:
        r+=1
        ins[lis[r]]+=1
        if ins[lis[r]]==1:
            zeroes-=1

        if 10**6-zeroes==k+1:
            ins[lis[r]]-=1
            zeroes+=1
            r-=1
            break

    if mL<r-l:
        mL=r-l
        pair=[l,r]

print(pair[0]+1,pair[1]+1)


n = input()
p = input()
n = n.split(' ')
k = int(n[1])
n = int(n[0])
p = p.split(' ')
p = [int(q) for q in p]
cnt = [0 for i in range(0,int(1e6 + 1))]
curcnt = 0
l = 0
r = -1
maxlen = -1
maxl = 0
maxr = 0
while r<n-1 and l<=n:
    while(r<n-1 and (curcnt + (cnt[p[r+1]] == 0)) <=k):
        curcnt = curcnt + (cnt[p[r+1]] == 0)
        cnt[p[r+1]] +=1 
        r+=1
    if maxlen <(r-l):
        maxlen = r-l
        maxr = r
        maxl = l
    cnt[p[l]]-=1
    curcnt-=(cnt[p[l]]==0)
    l+=1
print(str(maxl+1)+' '+str(maxr+1))

#16 3
#4 2 6 9 6 8 3 3 4 8 2 3 4 6 9 6
#13 3
#1 2 3 4 3 5 6 6 1 3 4 3 7
#16 3
#1 2 6 9 6 8 3 3 1 8 2 3 6 9 6


n = input()
p = input()
n = n.split(' ')
k = int(n[1])
n = int(n[0])
p = p.split(' ')
p = [int(q) for q in p]
cnt = [0]*(int(1e6+1))
curcnt = 0
l = 0
r = -1
maxlen = -1
maxl = 0
maxr = 0
while r<n-1 and l<=n:
    while(r<n-1 and (curcnt + (cnt[p[r+1]] == 0)) <=k):
        curcnt = curcnt + (cnt[p[r+1]] == 0)
        cnt[p[r+1]] +=1 
        r+=1
    if maxlen <(r-l):
        maxlen = r-l
        maxr = r
        maxl = l
    cnt[p[l]]-=1
    curcnt-=(cnt[p[l]]==0)
    l+=1
print(str(maxl+1)+' '+str(maxr+1))

#16 3
#4 2 6 9 6 8 3 3 4 8 2 3 4 6 9 6
#13 3
#1 2 3 4 3 5 6 6 1 3 4 3 7
#16 3
#1 2 6 9 6 8 3 3 1 8 2 3 6 9 6



def main():
    n, k = map(int,input().split())
    element_count = [0]*1000001

    count=0
    a = list(map(int, input().split()))
    s = 0
    res=0
    for t in range(n):
        element_count[a[t]] += 1
        if element_count[a[t]] == 1: count += 1
        while count > k:
            element_count[a[s]] -= 1
            if element_count[a[s]] == 0: count -= 1
            s +=1
        if t - s + 1 > res:
            res = t - s + 1
            l = s
            r = t

    print(l+1,r+1)


def __starting_point():
    main()
__starting_point()


def main():
    n, k = map(int,input().split())
    a = list(map(int, input().split()))
    element_count = [0]*1000001
    count=0
    s = 0
    res=0
    for t in range(n):
        element_count[a[t]] += 1
        if element_count[a[t]] == 1: count += 1
        while count > k:
            element_count[a[s]] -= 1
            if element_count[a[s]] == 0: count -= 1
            s +=1
        if t - s + 1 > res:
            res = t - s + 1
            l = s
            r = t
    print(l+1,r+1)


def __starting_point():
    main()
__starting_point()


def main():
    n,k = list(map(int, input().split()))
    myList = list(map(int, input().split()))
    #n,k = 5,5
    #myList = [1,2,3,4,5]
    i = 0
    distinct = 0
    dictOf = [0]*1000001
    best = 0
    bestX = 0
    bestY = 0
    for j in range(n):
        dictOf[myList[j]] += 1
        if dictOf[myList[j]] == 1:
            distinct += 1
        while distinct > k:
            dictOf[myList[i]] -= 1
            if dictOf[myList[i]] == 0:
                distinct -= 1
            i += 1
        if j-i+1 > best:
            best = j-i+1
            bestX = i+1
            bestY = j+1
    print(bestX, bestY)

def __starting_point():
    main()
    


__starting_point()

R = lambda: map(int, input().split())
n, k = R()
arr = list(R())
rl, rr = 0, 0
l = 0
rec = {}
for r, v in enumerate(arr):
    rec.setdefault(v, 0)
    rec[v] += 1
    while len(rec) > k:
        rec[arr[l]] -= 1
        if not rec[arr[l]]:
            rec.pop(arr[l])
        l += 1
    if rr - rl < r - l:
        rl, rr = l, r
print(rl + 1, rr + 1)

def solve(n, k, a):
	l, r, cur, answer_l, answer_r = 0, 0, 1, 0, 0

	cnt = [0 for _ in range(1000010)]
	cnt[a[0]] = 1

	while r + 1 < n:
		r += 1
		cnt[a[r]] += 1

		if cnt[a[r]] == 1:
			cur += 1

		if cur > k:
			if r - l - 1 > answer_r - answer_l:
				answer_l, answer_r = l, r - 1

		while cur > k:
			cnt[a[l]] -= 1
			
			if cnt[a[l]] == 0:
				cur -= 1

			l += 1

	if r - l > answer_r - answer_l:
		answer_l, answer_r = l, r

	print(answer_l + 1, answer_r + 1)


def __starting_point():
	n, k = list(map(int, input().split()))

	a = list(map(int, input().split()))

	solve(n, k, a)

__starting_point()

n, k = map(int, input().split())
a = list(map(int, input().split()))

cnt = [0] * 1000001
t = 0

left = 0
right = -1

l = 0
r = 0
while r < n:
    if cnt[a[r]] > 0: # already have this one
        cnt[a[r]] += 1
        r += 1
    elif t < k: # still has capacity
        cnt[a[r]] = 1
        t += 1
        r += 1
    else:
        # final answer for starting from l
        if r - l > right - left + 1:
            left = l
            right = r - 1

        # prepare for next answer
        cnt[a[l]] -= 1
        if cnt[a[l]] == 0:
            t -= 1
        l += 1

if r - l > right - left + 1:
    left = l
    right = r - 1

print(left + 1, right + 1)

def main():
  a = [int(x) for x in input().split()]
  g = 1
  mo = 0
  w = 1
  bigarray = [0]* 1000000
  rmo = []
  req = a[1]
  seq = [int(x) for x in input().split()]
  bigarray[seq[0]] += 1
  first = 0
  last = 0
  if a[0] == req:
    rmo = [1, a[0]]
  else:
    while first != len(seq) - 1:
      if w < req:
        if bigarray[seq[first + 1]] == 0:
          first += 1
          bigarray[seq[first]] += 1
          g = g + 1
          w = w + 1
        elif bigarray[seq[first + 1]] != 0:
          bigarray[seq[first + 1]] += 1
          first = first + 1
          g = g + 1
        if mo < g:
          mo = g
          rmo = [last + 1, first + 1]
      elif w >= req:
        if bigarray[seq[first + 1]] == 0:
          bigarray[seq[last]] -= 1
          if bigarray[seq[last]] == 0:
            w = w - 1
          if g > mo:
            mo = g
            rmo = [last + 1, first + 1]
          g = g - 1
          last = last + 1
        else:
          g = g + 1
          first += 1
          bigarray[seq[first]] += 1
          if mo < g:
            mo = g
            rmo = [last + 1, first + 1]
  for x in rmo:
    print(x, end = ' ')
main() 

def main():
  a = [int(x) for x in input().split()]
  g = 1
  mo = 0
  w = 1
  bigarray = [0]* 1000000
  rmo = []
  req = a[1]
  seq = [int(x) for x in input().split()]
  bigarray[seq[0]] += 1
  first = 0
  last = 0
  if a[0] == req:
    rmo = [1, a[0]]
  else:
    while first != len(seq) - 1:
      if w < req:
        if bigarray[seq[first + 1]] == 0:
          first += 1
          bigarray[seq[first]] += 1
          g = g + 1
          w = w + 1
        elif bigarray[seq[first + 1]] != 0:
          bigarray[seq[first + 1]] += 1
          first = first + 1
          g = g + 1
        if mo < g:
          mo = g
          rmo = [last + 1, first + 1]
      elif w >= req:
        if bigarray[seq[first + 1]] == 0:
          bigarray[seq[last]] -= 1
          if bigarray[seq[last]] == 0:
            w = w - 1
          if g > mo:
            mo = g
            rmo = [last + 1, first + 1]
          g = g - 1
          last = last + 1
        else:
          g = g + 1
          first += 1
          bigarray[seq[first]] += 1
          if mo < g:
            mo = g
            rmo = [last + 1, first + 1]
  for x in rmo:
    print(x, end = ' ')
main()
      

n,k=map(int,input().split())
l=[int(i) for i in input().split()]
maxi=0
left=-1 
right=-1 
ans=0
from collections import defaultdict 
d=defaultdict(int)
st=0 
end=0 
for end in range(n): 
    d[l[end]]+=1 
    if d[l[end]]==1:
        ans+=1 
    while ans>k: 
        d[l[st]]-=1 
        if d[l[st]]==0:
            ans-=1 
        st+=1 
    if end-st+1>maxi:
        maxi=end-st+1 
        left=st 
        right=end 


print(left+1,right+1)

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
ans = 0
cur_r = 0
d = {}
cur_ans = 0
ans_1 = 0
ans_2 = 0

for cur_l in range(n):
    t = a[cur_l]
    d[t] = d.get(t, 0)+1
    if d[t] == 1:
        cur_ans += 1

    while cur_ans > k:
        t = a[cur_r]
        d[t] -= 1
        if not(d[t]):
            cur_ans -= 1
        cur_r += 1

    if cur_l-cur_r+1 > ans:
        ans = cur_l-cur_r+1
        ans_1 = cur_r
        ans_2 = cur_l

print(ans_1+1, ans_2+1)


def longest(n,k,a):
    f = [0] * 1000001
    d = 0
    r = 0
    l = 0
    ans_l = 0
    ans_r = 0
    for r in range(0, n):
        f[a[r]] += 1
        if f[a[r]] == 1:
            d +=1
        while d > k:
            f[a[l]] -= 1
            if f[a[l]] == 0:
                d -= 1
            l += 1
        if ans_r - ans_l < r - l:
            ans_r = r
            ans_l = l
    return str(ans_l + 1) + " "+ str(ans_r + 1)
line_1 = list(map(int, input().split()))
n = line_1[0]
k = line_1[1]
line_2 = list(map(int, input().split()))

print(longest(n, k, line_2))
"""
5 5
1 2 3 4 5
"""
"""
9 3
6 5 1 2 3 2 1 4 5
"""
"""
3 1
1 2 3
"""