Painting Galary

Problem Statement

博览馆正在展出由世上最佳的 $m$ 位画家所画的图画。

游客在购买门票时必须说明两个数字，$a$ 和 $b$，代表他要看展览中的第 $a$ 幅至第 $b$ 幅画（包含 $a,b$）之间的所有图画，而门票的价钱就是一张图画一元。

Sept 希望入场后可以看到所有名师的图画。当然，他想最小化购买门票的价格。

请求出他购买门票时应选择的 $a,b$，数据保证一定有解。

若存在多组解，输出 $a$ 最小的那组。

Input

第一行两个整数 $n,m$，分别表示博览馆内的图画总数及这些图画是由多少位名师的画所绘画的。

第二行包含 $n$ 个整数 $a_i$，代表画第 $i$ 幅画的名师的编号。

Output

一行两个整数 $a,b$。

Sample Input

1
2


12 5
2 5 3 1 3 2 4 1 1 5 4 3

Output

1

2 7

Constraints

对于 $30%$ 的数据，有 $n\le200$，$m\le20$。
对于 $60%$ 的数据，有 $n\le10^5$，$m\le10^3$。
对于 $100%$ 的数据，有 $1\leq n\le10^6$，$1 \leq a_i \leq m\le2\times10^3$。

Solving

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


const int N = 1e6+100;
const int M = 0; 
int n,m;
int arr[N];
void solve()
{
    cin >> n >> m;
    set<int> st;
    map<int,int> mp;
    for(int i=1;i<=n;i++)
    {
        cin >> arr[i];
    }
    int l,r;
    int ans = INF;
    int left = 1;
    for(int right=1;right<=n;right++)
    {
        mp[arr[right]]++;
        st.insert(arr[right]);
        while((int)st.size()==m)
        {
            int curlen = right - left + 1;
            if(curlen < ans)
            {
                l = left;
                r = right;
                ans = curlen;
            }
            mp[arr[left]]--;
            if(mp[arr[left]]==0)
            {
                st.erase(arr[left]);
            }
            left++;
        }
    }
    cout << l << ' ' << r;
}