#include <iostream>
#include <algorithm>

using namespace std;

const int NMAX = 1e5;

int n, m, k;

int v[NMAX + 5];
int last[NMAX + 5];
int poz[NMAX + 5];
int tree[NMAX + 5];

struct QUERY
{
    int l;
    int r;
    int pos;
    int ans;
} q[NMAX + 5];

bool cmp(QUERY a, QUERY b)
{
    if (a.r > b.r)
    {
        poz[a.pos] = b.pos;
        return 1;
    }
    return 0;
}

void update(int where, int val)
{
    for (; where <= n; where += where & (-where))
        tree[where] += (val * v[where]);
}

int query(int where)
{
    int sum = 0;
    for (; where >= 1; where -= where & (-where))
        sum += tree[where];
    return sum;
}
int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
        last[v[i]] = -1;
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> q[i].l >> q[i].r;
        q[i].pos = i;
        q[i].ans = 0;
    }
    sort(q + 1, q + m + 1, cmp);

    int it = 1;
    for (int i = 1; i <= n; i++)
    {
        if (last[i] != -1)
            update(last[i], -1);
        last[i] = i;
        update(last[i], i);

        while (q[it].r == i && it <= m)
        {
            q[it].ans = query(q[it].r) - query(q[it].l - 1);
        }
    }
}