#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define ll long long

using namespace std;

const int N=5e4+,M=;

int n,m,w,base,a[N],cnt[M][N],ct[N];

ll sm[M][M],ans;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='') ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return fx?ret:-ret;

}

int bh(int a){return (a-)/base+;}

void init()

{

  int R=bh(n);

  for(int i=;i<=R;i++)

    {

      int t=i*base,j=i;

      if(t>n)

    {

      t=(i-)*base;

      for(int k=t+;k<=n;k++)

        sm[i][i]+=(cnt[i][a[k]]<<)+,cnt[i][a[k]]++;

      j=i-;

    }

      for(;t;j--)

    {

      sm[i][j]+=sm[i][j+];//

      for(int k=;k<=base;k++,t--)

        {

          sm[i][j]+=(cnt[i][a[t]]<<)+;

          cnt[i][a[t]]++;

        }

    }

    }

}

int main()

{

  n=rdn(); m=rdn(); w=rdn();

  base=sqrt(n);

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

  init();

  for(int i=,l,r,u,v;i<=m;i++)

    {

      l=rdn(); r=rdn(); u=bh(l); v=bh(r);

      if(v-u<=)

    {

      ans=;

      for(int j=l;j<=r;j++) ct[a[j]]=;

      for(int j=l;j<=r;j++)

        ans+=(ct[a[j]]<<)+,ct[a[j]]++;

      printf("%lld\n",ans);continue;

    }

      ans=sm[v-][u+];

      int L=u*base,R=(v-)*base;

      for(int j=l;j<=L;j++)

    {

      ans+=((cnt[v-][a[j]]-cnt[u][a[j]])<<)+;

      cnt[v-][a[j]]++;

    }

      for(int j=R+;j<=r;j++)

    {

      ans+=((cnt[v-][a[j]]-cnt[u][a[j]])<<)+;

      cnt[v-][a[j]]++;

    }

      for(int j=l;j<=L;j++) cnt[v-][a[j]]--;

      for(int j=R+;j<=r;j++) cnt[v-][a[j]]--;

      printf("%lld\n",ans);

    }

  return ;

}