出题人丧尽天良，正确算法也要卡掉。。。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define lowbit(x) (x & -(x))
#define gc() (p1 == p2 ? (p2 = buf + fread(p1 = buf, 1, 1 << 20, stdin), p1 == p2 ? EOF : *p1++) : *p1++)

using namespace std;

char buf[1 << 21], *p1, *p2;
constexpr int N = 2000010;
int n, T, a[N];
int pre[N], rub[N], k;
int ans[N], cnt, c[N];

struct node {
  node(int _a = 0, int _b = 0, int _c = 0, int _id = 0) : a(_a), b(_b), c(_c), id(_id) {}
  int a, b, c, id, res = 0;
} b[N << 1], cpy[N << 1];

inline void add(const int x, const int val) { for (int i = x; i <= n; i += lowbit(i)) c[i] += val; return; }
inline int ask(const int x) { int res = 0; for (int i = x; i; i &= i - 1) res += c[i]; return res; }

/*
pre_i + 1 <= l
-i <= -l
i <= r
*/

inline void Read(int &x)
{
  static char ch;
  for (ch = gc(); ch <= 32; ch = gc());  
  for (; ch > 32; ch = gc()) x = (x << 1) + (x << 3) + (ch ^ 48);
  return;
}

inline void Write(const int x)
{
  return (x > 9 ? Write(x / 10) : (void)putchar(10)), putchar(x % 10 ^ 48), void();
}

void cdq(const int l, const int r)
{
  if (l == r) return;

  const int mid = (l + r) >> 1;
  cdq(l, mid); cdq(mid + 1, r);

  // static auto cmp = [&](const node &A, const node &B) {
  //   if (A.b != B.b) return A.b < B.b;
  //   return A.c < B.c;
  // };

  // sort(b + l, b + mid + 1, cmp);
  // sort(b + mid + 1, b + r + 1, cmp);

  int i = l, j = mid + 1, tmp = l - 1;

  while (i <= mid && j <= r)
  {
    if (b[i].b <= b[j].b)
    {
      if (!b[i].id) add(b[i].c, 1);
      cpy[++tmp] = b[i++];
    }
    else 
    {
      if (b[j].id) b[j].res += ask(b[j].c);
      cpy[++tmp] = b[j++];
    }
  }
  // while (j <= r)
  // {
  //   while (i <= mid && b[i].b <= b[j].b)
  //   {
  //     if (!b[i].id) add(b[i].c, 1);
  //     i++;
  //   }
  //   if (b[j].id) b[j].res += ask(b[j].c);
  //   j++;
  // }

  while (j <= r) 
  {
    if (b[j].id) b[j].res += ask(b[j].c);
    cpy[++tmp] = b[j++];
  }
  for (int p = l; p != i; p++)
    if (!b[p].id)
      add(b[p].c, -1);
  while (i <= mid) cpy[++tmp] = b[i++];

  for (int p = l; p <= r; p++) b[p] = cpy[p];
  
  return;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);

  Read(n); Read(k); Read(T);
  pre[0] = n;

  for (int i = 1; i <= n; i++) Read(a[i]);

  for (int i = 1; i <= n; i++)  
  {
    pre[i] = rub[a[i]];
    rub[a[i]] = i;
  } 

  for (int i = 1; i <= n; i++)
    b[++cnt] = node(pre[pre[i]] + 1, -pre[i], i, 0);

  // cin >> T;

  for (int i = 1; i <= T; i++)
  {
    int l(0), r(0); Read(l); Read(r);
    b[++cnt] = node(l, -l, r, i);
  }

  sort(b + 1, b + cnt + 1, [&](const node &A, const node &B) {
    if (A.a != B.a) return A.a < B.a;
    if (A.b != B.b) return A.b < B.b;
    return A.c < B.c;
  });

  cdq(1, cnt);

  for (int i = 1; i <= cnt; i++)
    if (b[i].id)
      ans[b[i].id] = b[i].res;

  printf("%d", ans[1]);
  for (int i = 2; i <= T; i++) Write(ans[i]);

  return 0;
}