#include <cstdio>
#include <algorithm>
#include <cmath>
#include <deque>

using namespace std;

struct str
{
    int st,dr,poz;
};

str v1[200010],v2[200010];
deque<int> q[200010];
int v[200010];

int cmp1(str a,str b)
{
    return a.st<b.st;
}

int cmp2(str a,str b)
{
    return a.dr<b.dr;
}

int main()
{
    freopen("calafat.in","r",stdin);
    freopen("calafat.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&v[i]);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&v1[i].st,&v1[i].dr);
        v1[i].poz=i;
    }
    sort(v1+1,v1+m+1,cmp1);
    int bucket=sqrt(n),poz=1,poz1=1;
    while(poz<=n)
    {
        int l=0;
        while(poz1<=m && v1[poz1].st>=poz && v1[poz1].st<=poz+bucket-1) {v2[++l]=v1;poz1++;}
        if(l==0) {poz+=bucket;continue;}
        sort(v2+1,v2+l+1,cmp2);
        int a=v2[1].st,b=v2[1].dr,sol=0;
        for(int i=a;i<=b;i++)
        {
            if(mn[v[i]]==0) mn[v[i]]=mx[v[i]]=i;
            else {sol+=i-mx[v[i]];mx[v[i]]=i;}
            q[v[i]].push_back(i);
        }
        rez[v2[1].poz]=sol;
        for(int i=2;i<=l;i++)
        {
            for(int j=b+1;j<=v2[i].dr;j++)
            {
                if(mn[v[i]]==0) mn[v[i]]=mx[v[i]]=i;
                else {sol+=i-mx[v[i]];mx[v[i]]=i;}
                q[v[i]].push_back(i);
            }
            b=v2[i].dr;
            if(v2[i].st<a)
            {
                for(int j=a-1;j>=v2[i].st;j++)
                {
                    sol+=mn[v[j]]-j;
                    mn[v[j]]=j;
                    q[v[i]].push_front(i);
                }
                a=v2[i].st;
            }
            else if(v2[i].st>a)
            {
                for(int j=a;j<v2[i].st;j++)
                {
                    q[v[j]].pop_front();
                    if(q[v[j]].size()>0)
                }
            }
        }
    }
    return 0;
}