#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define pb push_back
#define lowbit(x) ((x)&(-x))
#define MAXN 300010
ll n,q,k;
ll a[MAXN];

// 树状数组
void add(vector<ll>&arr,ll x,ll y) {
  for(; x <= n; x += lowbit(x)){
    arr[x] += y;
  }
}
ll sum(vector<ll>&arr,ll x) {
  ll ans = 0;
  for(; x > 0; x -= lowbit(x)){
    ans += arr[x];
  }
  return ans;
}
ll sto(vector<ll>&arr,ll l,ll r) {
  return sum(arr,r) - sum(arr,l-1);
}

// [值] = 下标数组
vector<ll>v[MAXN];
// 离线 询问
struct ask {
  ll l,r,i;
}w[MAXN];

ll ans[MAXN];

bool cmp(ask a,ask b) {
  return a.r > b.r;
}

// < k
void solve(ll k,ll pw) {
  priority_queue< pair<ll,ll>,vector<pair<ll,ll>>, greater<pair<ll,ll>> >p; // {idx,value}
  rep(i,1,n+1){
    if(v[i].size() >= k){
      // 首个超过 k个的坐标和值
      p.push({v[i][k-1],i});
    }
  }
  vector<ll> cnt(MAXN,0);
  vector<ll>l2r(MAXN,0); // 以i为区间左端点，右侧端点选取(>=k)范围的左侧
  vector< vector<ll> > r2l(MAXN,vector<ll>());
  rep(i,1,n+1){
    while(!p.empty() && (
          // 之后的部分个数 小于k
          cnt[p.top().second] + k-1 >= v[p.top().second].size() ||
          // 每次用完了头部不pop，靠这个来避免重复？
          v[p.top().second][cnt[p.top().second] + k-1] != p.top().first
          )){
      p.pop();
    }
    // 扫描到当前 a[i] 出现的次数
    cnt[a[i]] ++;
    // 后续可出现连续 k个a[i]
    if(v[a[i]].size() > cnt[a[i]]+k-1){
      p.push({v[a[i]][cnt[a[i]]+k-1],a[i]});
    }
    l2r[i] = p.empty()?n:(p.top().first - 1);
    // 右侧区间的左侧坐标 -> 左端点, 从i到f[i] 这一段 最大次数小于k
    r2l[l2r[i]].pb(i);
  }

  // [0->i]为左端点不合法个数前缀和
  vector<ll>s(MAXN,0);
  rep(i,1,n+1){
    // 表示<k的对的方案数
    s[i] = s[i-1] + l2r[i]-i+1;
  }
  // 树状数组
  vector<vector<ll> >tr(2, vector<ll>(MAXN,0));
  ll nn = 0;
  // 询问从右向左处理
  per(i,1,n+1){
    while(w[nn].r >= i && nn < q) {
      ans[w[nn].i] += pw*(
          // 小于k 的对数方案
          (s[w[nn].r] - s[w[nn].l-1])
          // 当前  大于k 的对数方案
          +sto(tr[0],w[nn].l,w[nn].r)+w[nn].r*sto(tr[1],w[nn].l,w[nn].r)
      );
      nn ++;
    }
    rep(j,0,r2l[i].size()){
      ll xay = r2l[i][j];
      // 大于等于k的对数
      add(tr[0],xay,-i);
      // 次数
      add(tr[1],xay,1);
    }
  }
}

int main() {
  scanf("%lld %lld %lld",&n,&q,&k);
  rep(i,1,n+1){
    cin >> a[i];
    v[a[i]].pb(i);
  }
  rep(i,0,q){
    scanf("%lld %lld",&w[i].l,&w[i].r);
    w[i].i = i;
  }
  // 询问 右侧r 从大到小排列
  sort(w,w+q,cmp);

  solve(k+1,1);
  if(k != 1){
    solve(k,-1);
  }
  rep(i,0,q){
    printf("%lld\n",ans[i]);
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,n) for (int i=a;i<n;i++)

int ia = 0;
int a[20];
int ib = 0;
int b[20];

int possible = 0;

int N = 12;

bool test_possible(){
  if(ia != ib)return false;
  int gcnt=0;
  int lcnt=0;
  rep(i,0,ia){
    if(a[i]< b[i]){
      lcnt++;
    }else{
      gcnt++;
    }
  }
  return lcnt != 0 && gcnt != 0;
}

void tryidx(int index){
  if(index == N){
    possible += test_possible();
    return;
  }
  a[ia++] = index;
  tryidx(index+1);
  ia--;
  if(ia != 0){
    b[ib++] = index;
    tryidx(index+1);
    ib--;
  }

  tryidx(index+1);
}


int main(){
  cin>>N;
  tryidx(0);
  printf("%d\n",possible);
  return 0;
}