Amr has got a large array of size n. Amr doesn't like large arrays so he intends to make it smaller.

Amr doesn't care about anything in the array except the beauty of it. The beauty of the array is defined to be the maximum number of times that some number occurs in this array. He wants to choose the smallest subsegment of this array such that the beauty of it will be the same as the original array.

Help Amr by choosing the smallest subsegment possible.


-----Input-----

The first line contains one number n (1 ≤ n ≤ 10^5), the size of the array.

The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 10^6), representing elements of the array.


-----Output-----

Output two integers l, r (1 ≤ l ≤ r ≤ n), the beginning and the end of the subsegment chosen respectively.

If there are several possible answers you may output any of them. 


-----Examples-----
Input
5
1 1 2 2 1

Output
1 5
Input
5
1 2 2 3 1

Output
2 3
Input
6
1 2 2 1 1 2

Output
1 5


-----Note-----

A subsegment B of an array A from l to r is an array of size r - l + 1 where B_{i} = A_{l} + i - 1 for all 1 ≤ i ≤ r - l + 1

Difficulty: interview

Starter code:

Solutions:
import collections

n = int(input())
As = list(map(int, input().split()))

def solve(n, As):
    counter = collections.Counter(As)
    candidates = []
    prev_freq = 0
    for num, freq in counter.most_common():
        if prev_freq and prev_freq!= freq:
            break
        candidates.append(num)
        prev_freq = freq
    lr = {cand:[] for cand in candidates}
    for i, a in enumerate(As, 1):
        if a in lr:
            lr[a].append(i)
    minspan = float('inf')
    for pos in list(lr.values()):
        if pos[-1] - pos[0] < minspan:
            minspan = pos[-1] - pos[0]
            LR = (pos[0], pos[-1])
    return LR

print(*solve(n, As))


import math,string,itertools,fractions,heapq,collections,re,array,bisect,copy
from itertools import chain, dropwhile, permutations, combinations
from collections import defaultdict, deque

# Guide:
#   1. construct complex data types while reading (e.g. graph adj list)
#   2. avoid any non-necessary time/memory usage
#   3. avoid templates and write more from scratch
#   4. switch to "flat" implementations

def VI(): return list(map(int,input().split()))
def I(): return int(input())
def LIST(n,m=None): return [0]*n if m is None else [[0]*m for i in range(n)]
def ELIST(n): return [[] for i in range(n)]
def MI(n=None,m=None): # input matrix of integers
    if n is None: n,m = VI()
    arr = LIST(n)
    for i in range(n): arr[i] = VI()
    return arr
def MS(n=None,m=None): # input matrix of strings
    if n is None: n,m = VI()
    arr = LIST(n)
    for i in range(n): arr[i] = input()
    return arr
def MIT(n=None,m=None): # input transposed matrix/array of integers
    if n is None: n,m = VI()
    a = MI(n,m)
    arr = LIST(m,n)
    for i,l in enumerate(a):
        for j,x in enumerate(l):
            arr[j][i] = x
    return arr


def run(n,x,l,r):
    s = 0
    curr = 1
    for i in range(n):
        skip = (l[i]-curr) // x
        s += r[i]-curr-skip*x+1
        curr = r[i]+1
    print(s)


def main(info=0):
    n = I()
    a = VI()

    d = {}
    for i,x in enumerate(a):
        if x in d:
            (l,r,num) = d[x]
            d[x] = (l, i, num+1)
        else:
            d[x] = (i,i,1)

    best = (0, 1e7)
    bestv = None
    for k,v in list(d.items()):
        (l,r,num) = v
        dist = r-l+1
        if (num, -dist) > best:
            best = (num, -dist)
            bestv = v

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

def __starting_point():
    main()

__starting_point()

n=int(input())
mas=list(map(int,input().split(" ")))
dic={i:[0,-1,-1] for i in set(mas)}
ma=0
for i in range(n):
    if  dic[mas[i]][1]==-1:
        dic[mas[i]][1]=i
    dic[mas[i]][0]+=1
    dic[mas[i]][2]=i
    if dic[mas[i]][0]>ma:ma=dic[mas[i]][0]
mi=9999999999
a=0
b=0
for i in range(n):
    if(dic[mas[i]][0]==ma and dic[mas[i]][2]-dic[mas[i]][1]<mi):
        a=dic[mas[i]][1]
        b=dic[mas[i]][2]
        mi=b-a
print(a+1,b+1)



N = int(input())
A = [int(x) for x in input().split()]
bucket = dict()
for i, num in enumerate(A):
    if num in bucket:
        bucket[num].append(i)
    else:
        bucket[num] = [i]
#print(bucket)
sorted_buckets = sorted((-len(val), val[-1]-val[0], val) for _, val in list(bucket.items()))
print(sorted_buckets[0][2][0]+1, sorted_buckets[0][2][-1]+1)


#!/usr/bin/env python
# -*- coding: utf-8 -*-
counter = dict()
max_num = (0,0)

n = int(input())
A = list(map(int,input().split()))

for i in range(len(A)):
    if A[i] in counter:
        counter[A[i]][0] += 1
        counter[A[i]][2] = i
    else:
        counter[A[i]] = [1,i,i]

count,l,r = max(list(counter.values()),key = lambda x:(x[0],-(x[2]-x[1]),-x[1]))
print(l+1,r+1)


n = int(input())

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

d = {}

for i in range(n):
	if arr[i] not in d:
		d[arr[i]] = (i,i,1)
	else:
		x = d[arr[i]]
		y = (x[0],i,x[2]+1)
		d[arr[i]] = y

#print(d)

p = 10**20
r = 0

for i in d:
	m = d[i]
	if(m[2] > r):
		r = m[2]
		p = m[1]-m[0]
		q = m[0],m[1]
	elif(m[2] == r and (m[1] - m[0]) < p):
		r = m[2]
		p = m[1]-m[0]
		q = (m[0],m[1])

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

def cmp_to_key(mycmp):
    'Convert a cmp= function into a key= function'

    class K:
        def __init__(self, obj, *args):
            self.obj = obj

        def __lt__(self, other):
            return mycmp(self.obj, other.obj) < 0

        def __gt__(self, other):
            return mycmp(self.obj, other.obj) > 0

        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0

        def __le__(self, other):
            return mycmp(self.obj, other.obj) <= 0

        def __ge__(self, other):
            return mycmp(self.obj, other.obj) >= 0

        def __ne__(self, other):
            return mycmp(self.obj, other.obj) != 0

    return K


def compare(x, y):
    if x[2] != y[2]:
        return y[2] - x[2]
    return (x[1] - x[0]) - (y[1] - y[0])


def main():
    n = int(input())
    d = list(map(int, input().split()))
    r = {}
    for i in range(n):
        if d[i] in r:
            r[d[i]] = [r[d[i]][0], i + 1, r[d[i]][2]+1]
        else:
            r[d[i]] = [i + 1, i + 1, 1]

    sr = sorted(list(r.values()), key=cmp_to_key(compare))
    print(sr[0][0], sr[0][1])


main()


num = int(input())
data = dict()

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

for i in range(num):
    if lst[i] in data:
        data[lst[i]][0] += 1
        data[lst[i]][2] = i
    else:
        data[lst[i]] = [1, i, i]

m = 1;
newlst = []
for n in data.keys():
    info = data[n]
    if info[0] > m:
        m = info[0]
        newlst = [info[1:]]
    elif info[0] == m:
        newlst += [info[1:]]

mn = num + 1
best = []
newlst = sorted(newlst)
for i in range(len(newlst)):
    rng = newlst[i][1] - newlst[i][0]
    if rng < mn:
        mn = rng
        best = newlst[i]

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

N = int(input())
a = [int(i) for i in input().split()]
d = {}
b = {}
for i, f in enumerate(a):
    if f not in d:
        d[f] = 0
        b[f] = [i, i]
    d[f] += 1
    b[f][1] = i

mn = max(d.values())

m = [0, N]

for k in list(d.keys()):
    if d[k] != mn:
        continue

    if b[k][1] - b[k][0] < m[1] - m[0]:
        m = b[k]

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


mm = 0
mmi = []
f = [0]*(10**6+5)
g = [[] for _ in range(10**6+5)]
x = int(input())
l = list(map(int, input().split(' ')))
for i in range(x):
    f[l[i]]+= 1
    g[l[i]].append(i+1)
    if f[l[i]] > mm:
        mm = f[l[i]]
        mmi = [l[i]]
    elif f[l[i]] == mm:
        mmi.append(l[i])

a1 = 0
a2 = 0
minn = 1000000000
for i in mmi:
    if g[i][-1] - g[i][0] < minn:
        minn = g[i][-1] - g[i][0]
        a1 = g[i][0]
        a2 = g[i][-1]
        
print(a1, a2)


def bin_search(n,a):
    l = 0
    r = len(a)-1
    while l<=r:
        m = (l+r)//2
        if n>a[m][0]:
            l = m+1
        if n<a[m][0]:
            r = m-1
        if n == a[m][0]:
            return m
    return -1
n = int(input())
a = input().split()
def ke(n):
    return n[1]
def f(n):
    return abs(n[2]-n[3])
cnt = {}
mx = 0
for i in range(n):
    a[i] = int(a[i])
    if a[i] in cnt:
        cnt[a[i]][1] += 1
        cnt[a[i]][3] = i
    else:
        cnt[a[i]] = [a[i],1,i,0]
for m in list(cnt.values()):
    if m[1]>mx:
        mx = m[1]
v = []
for m in list(cnt.values()):
    if m[1]==mx:
        v.append(m)
v.sort(key=f)
print(v[0][2]+1,v[0][3]+1)


#!/usr/bin/env python
# -*- coding: utf-8 -*-
from collections import Counter


def solve(n, xs):
    rxs = list(reversed(xs))
    length = len(xs)
    counter = {}
    # counter = Counter(xs)
    # m = counter.most_common(1)[0][1]
    for i, x in enumerate(xs):
        if x in counter:
            counter[x]['cnt'] += 1
            counter[x]['last'] = i
        else:
            counter[x] = {'cnt': 0, 'first': i, 'last': i}
    ts = sorted(list(counter.items()), key=lambda t: t[1]['cnt'], reverse=True)
    maxs = []
    mv = 0  # max value
    mr = float('inf')  # max range
    rkey = 0  # result key
    for t in ts:
        k, d = t
        r = d['last'] - d['first']
        if mv <= d['cnt'] and mr > r:
            mv = d['cnt']
            mr = r
            rkey = k
    return counter[rkey]['first'] + 1, counter[rkey]['last'] + 1
    # maxs = map(lambda x: x[0], filter(lambda x: x[1] == m, counter.most_common()))
    # r = float('inf')
    # rf = 0
    # rl = 0
    # for x in maxs:
    #     first = xs.index(x)
    #     last = length - rxs.index(x) - 1
    #     l = last - first + 1
    #     if r > l:
    #         r = l
    #         rf = first
    #         rl = last
    # return rf + 1, rl + 1


def getinput():
    def getints_line():
        return list(map(int, input().split(' ')))
    n = int(input())
    xs = getints_line()
    return n, xs


def test():
    # print(solve(5, [1, 1, 2, 2, 1]))
    # print(solve(5, [1, 2, 2, 3, 1]))
    # print(solve(6, [1, 2, 2, 1, 1, 2]))
    assert solve(5, [1, 1, 2, 2, 1]) == (1, 5)
    assert solve(5, [1, 2, 2, 3, 1]) == (2, 3)
    assert solve(6, [1, 2, 2, 1, 1, 2]) == (1, 5)


def main():
    # test()
    # print(*getinput())
    print(' '.join(map(str, solve(*getinput()))))
    # print('\n'.join(map(str, solve(*getinput()))))

def __starting_point():
    main()

__starting_point()

N = int(input())
A = [int(x) for x in input().split()]

bucket = dict()
for i, num in enumerate(A):
    if num in bucket:
        bucket[num].append(i)
    else:
        bucket[num] = [i]

sorted_buckets = sorted(list(bucket.values()), key=lambda val: (-len(val), val[-1]-val[0]))
print(sorted_buckets[0][0]+1, sorted_buckets[0][-1]+1)


from collections import defaultdict
N = int(input())
A = [int(x) for x in input().split()]

bucket = defaultdict(list)
for i, num in enumerate(A):
    bucket[num].append(i)

sorted_buckets = sorted(list(bucket.values()), key=lambda val: (-len(val), val[-1]-val[0]))
print(sorted_buckets[0][0]+1, sorted_buckets[0][-1]+1)