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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int v[500000], st, dr, n, frecv[1000001], maxim, stfinal, drfinal, k, i;
int readInt() {
  int raspuns = 0;
  char ch;
  bool minus = false;
  ch = getchar();
  if (ch == '-')
    minus = true;
  else
    raspuns = ch - '0';
  while (true) {
    ch = getchar();
    if (ch < '0' || ch > '9') break;
    raspuns = raspuns * 10 + (ch - '0');
  }
  if (minus == true) return -raspuns;
  return raspuns;
}
int main() {
  n = readInt();
  k = readInt();
  for (i = 0; i < n; ++i) v[i] = readInt();
  st = 0;
  dr = 0;
  stfinal = 0;
  while (k && dr < n) {
    if (frecv[v[dr]] == 0) {
      --k;
    }
    ++frecv[v[dr]];
    ++dr;
  }
  while (frecv[v[dr]] && dr < n) {
    ++frecv[v[dr]];
    ++dr;
  }
  --dr;
  maxim = dr - st;
  drfinal = dr;
  while (dr < n) {
    while (frecv[v[st]] - 1 != 0) {
      --frecv[v[st]];
      ++st;
    }
    --frecv[v[st]];
    ++st;
    ++k;
    ++dr;
    while (k > 0 && dr <= n) {
      if (frecv[v[dr]] == 0) {
        --k;
      }
      ++frecv[v[dr]];
      ++dr;
    }
    while (frecv[v[dr]] && dr < n) {
      ++frecv[v[dr]];
      ++dr;
    }
    --dr;
    if (maxim < dr - st) {
      maxim = dr - st;
      drfinal = dr;
      stfinal = st;
    }
  }
  cout << stfinal + 1 << " " << drfinal + 1;
  return 0;
}