#include<bits/stdc++.h>
using namespace std;
namespace fast_IO {
#define IOSIZE 100000
char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
inline void print(char x) { putchar(x); }
inline void print(char *x) { while (*x) putchar(*x++); }
inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
inline void print(bool b) { putchar(b+48); }
template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
const int N=1e5+10;
const int M=25000+10;
int n,m,e[N],s[N],blo[N],siz,cnt[N],ans[N];
int S;
bool vis[N];
struct Questions
{
int l,r,bll,idx;
inline bool operator < (const Questions &x) const {return blo[l]==blo[x.l]?blo[r]<blo[x.r]:blo[l]==blo[x.l];}
}q[N];
bitset<N> b[M],now;
inline void add(int pos)
{
int x=e[pos];
++cnt[x];
now[x+cnt[x]-1]=1;
return ;
}
inline void del(int pos)
{
int x=e[pos];
--cnt[x];
now[x+cnt[x]]=0;
return ;
}
inline void solve(int num)
{
siz=0;
memset(vis,0,sizeof vis);
memset(cnt,0,sizeof cnt);
memset(ans,0,sizeof ans);
for (int i=1;i<=num;i++)
for (int j=1;j<=3;j++)
{
q[++siz].idx=i;
cin>>q[siz].l>>q[siz].r;
ans[i]+=q[siz].r-q[siz].l+1;
}
now.reset();
sort(q+1,q+siz+1);
int l=1,r=0;
for (int i=1;i<=siz;i++)
{
while (l>q[i].l) add(--l);
while (r<q[i].r) add(++r);
while (l<q[i].l) del(l++);
while (r>q[i].r) del(r--);
if (!vis[q[i].idx]) b[q[i].idx]=now,vis[q[i].idx]=1;
else b[q[i].idx]&=now;
}
for (int i=1;i<=num;i++) ans[i]-=b[i].count()*3;
for (int i=1;i<=num;i++) cout<<ans[i]<<endl;
return ;
}
signed main()
{
cin>>n>>m;S=sqrt(n);
for (int i=1;i<=n;i++) cin>>e[i],s[i]=e[i],blo[i]=(i-1)/S+1;
sort(s+1,s+n+1);
for (int i=1;i<=n;i++) e[i]=lower_bound(s+1,s+n+1,e[i])-s;
int T=25000;
while (m)
{
if (m<T)
{
solve(m);
return 0;
}
else solve(T),m-=T;
}
return (0-0);
}