/**************************************************************

     Problem: 3781

     User: idy002

     Language: C++

     Result: Accepted

     Time:1184 ms

     Memory:2772 kb

 ****************************************************************/

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #define maxn 50010

 using namespace std;

 typedef long long lng;

 int n, m, k;

 int w[maxn];

 int mccno[maxn], lx[maxn], rx[maxn], stot;

 int cnt[maxn];

 lng ans[maxn], cur_ans;

 struct Qu {

     int l, r, id;

     bool operator<( const Qu & b ) const {

         return mccno[l]<mccno[b.l] || (mccno[l]==mccno[b.l] && r<b.r );

     }

 };

 Qu qu[maxn];

 void init() {

     memset( cnt, , sizeof(cnt) );

     cur_ans = ;

 }

 void add( int v ) {

     cur_ans -= cnt[v]*cnt[v];

     cnt[v]++;

     cur_ans += cnt[v]*cnt[v];

 }

 void del( int v ) {

     cur_ans -= cnt[v]*cnt[v];

     cnt[v]--;

     cur_ans += cnt[v]*cnt[v];

 }

 void partition() {

     int len = (int)sqrt(n)+;

     int stot = n/len;

     rx[] = ;

     for( int i=; i<=stot; i++ ) {

         lx[i] = rx[i-]+;

         rx[i] = rx[i-]+len;

     }

     if( rx[stot]!=n ) {

         stot++;

         rx[stot] = n;

         lx[stot] = rx[stot-]+;

     }

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

         for( int j=lx[i]; j<=rx[i]; j++ )

             mccno[j] = i;

 }

 void work() {

     sort( qu+, qu++m );

     for( int q=,lf,rg; q<=m; q++ ) {

         if( q== || mccno[qu[q].l]!=mccno[qu[q-].l] ) {

             lf = qu[q].l;

             rg = lf-;

             init();

         }

         while( lf<qu[q].l ) del( w[lf++] );

         while( lf>qu[q].l ) add( w[--lf] );

         while( rg<qu[q].r ) add( w[++rg] );

         while( rg>qu[q].r ) del( w[rg--] );

         ans[qu[q].id] = cur_ans;

     }

 }

 int main() {

     scanf( "%d%d%d", &n, &m, &k );

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

         scanf( "%d", w+i );

     for( int i=; i<=m; i++ ) {

         scanf( "%d%d", &qu[i].l, &qu[i].r );

         qu[i].id = i;

     }

     partition();

     work();

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

         printf( "%lld\n", ans[i] );

 }