rt

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    char ch=getchar();int x=0;bool f=1;
    while(ch<'0'||'9'<ch){if(ch=='-')f=0;ch=getchar();}
    while('0'<=ch&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return f?x:-x;
}
const int N=1e5+5,M=10002;
int n,m,a[N],pos[N],book[N];
struct qwq{
    int l,r,id;
    bitset<100001>bs;
}q[M*3];
vector<int>v;
bitset<100001>vis;
inline int getid(int x){
    return upper_bound(v.begin(),v.end(),x)-v.begin();
}
void sub(int x){
    book[a[x]]--;
    vis.reset(a[x]-book[a[x]]);
    return;
}
void add(int x){
    vis.set(a[x]-book[a[x]]);
    book[a[x]]++;
    return;
}
void solve(int T){
    vis.reset();
    for(int i=0;i<T;i++){
        q[i*3+1]={read(),read(),i*3+1};
        q[i*3+2]={read(),read(),i*3+2};
        q[i*3+3]={read(),read(),i*3+3};
    }
    sort(q+1,q+T*3+1,[](qwq x,qwq y){return pos[x.l]==pos[y.l]?x.r<y.r:pos[x.l]<pos[y.l];});
    for(int i=1,l=1,r=0;i<=T*3;i++){
        while(l>q[i].l)add(--l);
        while(r<q[i].r)add(++r);
        while(l<q[i].l)sub(l++);
        while(r>q[i].r)sub(r--);
        q[i].bs=vis;
    }
    sort(q+1,q+T*3+1,[](qwq x,qwq y){return x.id<y.id;});
    for(int i=0;i<T;i++){
        int siz=(q[i*3+1].bs&q[i*3+2].bs&q[i*3+3].bs).count();
        printf("%d\n",q[i*3+1].r-q[i*3+1].l+1+q[i*3+2].r-q[i*3+2].l+1+q[i*3+3].r-q[i*3+3].l+1-siz*3);
    }
    return;
}
signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    n=read();m=read();
    int ql=1000,bl=sqrt(n);
    for(int i=1;i<=n;i++)a[i]=read(),pos[i]=(i-1)/bl+1,v.push_back(a[i]);
    sort(v.begin(),v.end());
    for(int i=1;i<=n;i++)a[i]=getid(a[i]);
    while(m>ql)solve(ql),m-=ql;
    solve(m);
    return 0;
}