#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
struct ban
{
int t, l, r;
};
int n, m;
int s[N];
ban b[N];
int ss[N];
void solv1()
{
for (int i = 1; i <= m; ++i)
{
for (int j = 1; j <= n; ++j)
ss[j] = s[j];
for (int ii = 0; ii < b[i].t; ++ii)
{
for (int j = n; j >= 1; --j)
ss[j] = max(ss[j], ss[j - 1]);
}
long long ans = 0;
for (int j = b[i].l; j <= b[i].r; ++j)
ans += ss[j];
printf("%lld\n", ans);
}
}
int t[N * 4];
void bil(int tl, int tr, int pos)
{
if (tl == tr)
{
t[pos] = s[tl];
return;
}
int m = (tl + tr) / 2;
bil(tl, m, pos * 2);
bil(m + 1, tr, pos * 2 + 1);
t[pos] = max(t[pos * 2], t[pos * 2 + 1]);
}
int qry(int tl, int tr, int l, int r, int pos)
{
if (tl == l && tr == r)
return t[pos];
int m = (tl + tr) / 2;
if (r <= m)
return qry(tl, m, l, r, pos * 2);
if (l > m)
return qry(m + 1, tr, l, r, pos * 2 + 1);
return max(qry(tl, m, l, m, pos * 2),
qry(m + 1, tr, m + 1, r, pos * 2 + 1));
}
long long p[N];
void solv2()
{
bil(1, n, 1);
for (int i = 1; i <= n; ++i)
s[i] = qry(1, n, max(1, i - b[1].t), i, 1);
for (int i = 1; i <= n; ++i)
p[i] = p[i - 1] + s[i];
for (int i = 1; i <= m; ++i)
printf("%lld\n", p[b[i].r] - p[b[i].l - 1]);
}
void solv3()
{
bil(1, n, 1);
for (int i = 1; i <= m; ++i)
{
printf("%d\n", qry(1, n, max(1, b[i].l - b[i].t), b[i].l, 1));
}
}
int t1[N * 4];
void ubd1(int tl, int tr, int x, int pos)
{
if (tl == tr)
{
t1[pos] = 1;
return;
}
int m = (tl + tr) / 2;
if (x <= m)
ubd1(tl, m, x, pos * 2);
else
ubd1(m + 1, tr, x, pos * 2 + 1);
t1[pos] = t1[pos * 2] + t1[pos * 2 + 1];
}
int qry1(int tl, int tr, int l, int r, int pos)
{
if (l > r)
return 0;
if (tl == l && tr == r)
return t1[pos];
int m = (tl + tr) / 2;
return qry1(tl, m, l, min(m, r), pos * 2) +
qry1(m + 1, tr, max(m + 1, l), r, pos * 2 + 1);
}
int ans[N];
int u2[N];
vector<int> v[N];
vector<int> q[N];
void solv4()
{
for (int i = 1; i <= n; ++i)
{
u2[i] = u2[i - 1];
if (s[i] == 2)
u2[i] = i;
}
for (int i = 1; i <= n; ++i)
{
if (u2[i])
v[i - u2[i]].push_back(i);
}
for (int i = 1; i <= m; ++i)
{
q[b[i].t].push_back(i);
}
for (int i = 0; i <= n; ++i)
{
for (int j = 0; j < v[i].size(); ++j)
{
int x = v[i][j];
ubd1(1, n, x, 1);
}
for (int j = 0; j < q[i].size(); ++j)
{
int x = q[i][j];
ans[x] = qry1(1, n, b[x].l, b[x].r, 1) + (b[x].r - b[x].l + 1);
}
}
for (int i = 1; i <= m; ++i)
printf("%d\n", ans[i]);
}
int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", &s[i]);
for (int i = 1; i <= m; ++i)
{
scanf("%d%d%d", &b[i].t, &b[i].l, &b[i].r);
}
solv4();
return 0;
}
