wa了一大片。

样例过了。

我的思路是按x从大到小排序之后，相当于就是小根笛卡尔树上的从子节点往根节点上合并的过程。

然后我就把询问离线下来，按照x排序。

然后再对于hi建立笛卡尔树，每次找到第一个>x的点，把还没有更新的>x的点给开一下，然后把这个节点的子节点的所有的影响给删掉，这里我用的是线段树维护左端点来实现的，bit也可以，感觉线段树好写一点。

然后就查询这个区间内的左端点个数就可以了。

以上是我的思路。

#include <bits/stdc++.h>
#define lb(x) (x&-x)
#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)
#define swap(a,b) (a^=b^=a^=b)

using namespace std;
using i64 = long long;

typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
void chmin(int &x, int c) {
  x = min(x, c);
}
void chmax(ll &x, ll c) {
  x = max(x, c);
}

namespace fast_IO{
#define IOSIZE 100000
int precision=3,POW[10]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};char ibuf[IOSIZE],obuf[IOSIZE],*p1=ibuf,*p2=ibuf,*p3=obuf;
#ifdef ONLINE_JUDGE
#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)
#endif
template<typename T>inline T read(){T s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)&&(ch!=EOF))if(ch==45)w=-1;if(ch==EOF)return 0;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)&&(ch!=EOF))if(ch==45)w=-1;if(ch==EOF)return 0;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*=w,1;}inline bool read(char&s){while(s=getchar(),isspace(s));return 1;}inline bool read(char*s){char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return 0;while(!isspace(ch))*s++=ch,ch=getchar();*s='\000';return 1;}template<typename T>inline void print(T x){if(x<0)putchar(45),x=-x;if(x>9)print(x/10);putchar(x%10+48);}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 0;while(!isspace(ch))s+=ch,ch=getchar();return 1;}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 1;}inline void print(bool b){putchar(b+48);}inline bool read(double&x){int a=0,b=0;char ch=getchar();bool f=0;while(ch<48||ch>57){if(ch==45)f=1;ch=getchar();}while(47<ch&&ch<58){a=(a<<1)+(a<<3)+(ch^48);ch=getchar();}if(ch!=46){x=f?-a:a;return 1;}ch=getchar();while(47<ch&&ch<58){b=(b<<1)+(b<<3)+(ch^48),ch=getchar();}x=b;while(x>1)x/=10;x=f?-a-x:a+x;return 1;}inline void print(double x){if(x<0){putchar(45),x=-x;}x=round((long double)x*POW[precision])/POW[precision],print((long long)x),putchar(46),x-=(long long)(x);for(int i=1;i<=precision;i++)x*=10,putchar(x+48),x-=(int)x;}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 maxn = 4e5 + 10, mod = 1e9 + 7;
int N, Q, A[maxn], B[maxn], lg2[maxn];
int mn[maxn][20];
void init() {
	for (int i = 1; i <= N; i ++ ) {
		mn[i][0] = i;
	}
	for (int j = 1; j <= 19; j ++ )
		for (int i = 1; i + (1 << j) - 1 <= N; i ++ ) 
			if (A[mn[i][j - 1]] < A[mn[i + (1 << (j - 1))][j - 1]])
				mn[i][j] = mn[i][j - 1];
			else
				mn[i][j] = mn[i + (1 << (j - 1))][j - 1];
}
int query (int l, int r) {
	int k = lg2[r - l + 1];
	if (A[mn[l][k]] < A[mn[r - (1 << k) + 1][k]])
		return mn[l][k];
	return mn[r - (1 << k) + 1][k];
}
int lpos[maxn], rpos[maxn], fa[maxn];
int res[maxn], c[maxn];
struct qwq {
	int l, r, x, id;
} a[maxn];
struct node {
	int x, id;
} b[maxn];
vector<int> g[maxn];
void build (int u, int l, int r) {
	lpos[u] = l, rpos[u] = r;
	if (l >= r) return;
	int mid1 = query (l, u - 1);
	int mid2 = query (u + 1, r);
	if (mid1 < u) g[u].push_back(mid1);
	if (mid2 > u) g[u].push_back(mid2);
	fa[mid1] = fa[mid2] = u;
	build (mid1, l, u - 1);
	build (mid2, u + 1, r); 
}
int sum[maxn << 2];
void upd (int u, int l, int r, int x, int w) {
	if (l == r) {
		sum[u] = w; return;
	}
	int mid = (l + r) >> 1;
	if (x <= mid) upd (u << 1, l, mid, x, w);
	else upd (u << 1 | 1, mid + 1, r, x, w);
	sum[u] = sum[u << 1] + sum[u << 1 | 1];
}
int query (int u, int l, int r, int ql, int qr) {
	if (ql <= l && qr >= r) {
		return sum[u];
	}
	int S = 0, mid = (l + r) >> 1;
	if (ql <= mid) S = query (u << 1, l, mid, ql, qr);
	if (qr > mid) S += query (u << 1 | 1, mid + 1, r, ql, qr);
	return S;
}

void solve() {
	cin >> N >> Q;
	for (int i = 2; i <= N; i ++ ) {
		lg2[i] = lg2[i >> 1] + 1;
	}
	for (int i = 1; i <= N; i ++ ) {
		cin >> A[i];
		b[i].x = A[i], b[i].id = i;
	}
	if (N <= 2000 && Q <= 2000) {
		for (int i = 1; i <= N; i ++ ) {
			B[i] = A[i];
		}
		for (int i = 1; i <= Q; i ++ ) {
			int l, r, x;
			cin >> l >> r >> x;
			for (int j = 1; j <= N; j ++ )
				A[j] = B[j];
			for (int j = 1; j <= N; j ++ )
				A[j] -= x;
			bool f = 0;
			int res = 0;
			for (int j = l; j <= r; j ++ ) {
				if (A[j] <= 0) {
					f = 0;
				} else {
					res += !f, f = 1;
				}
			}
			cout << res << '\n';
		} 
		return ;
	}
	init();
	build (query(1, N), 1, N);
	for (int i = 1; i <= Q; i ++ ) {
		cin >> a[i].l >> a[i].r >> a[i].x;
		a[i].id = i;
	}
	sort (a + 1, a + 1 + Q, [](qwq i, qwq j){
		return i.x > j.x;
	});
	sort (b + 1, b + 1 + N, [](node i, node j){
		return i.x < j.x;
	});
	for (int i = 1; i <= N; i ++ ) c[i] = b[i].x;
//	for (int i = 1; i <= Q; i ++ ) {
//		cout << a[i].l << ' ' << a[i].r << ' ' << a[i].x << '\n';
//	}
//	for (int i = 1; i <= N; i ++ ) {
//		cout << c[i] << " \n"[i == N];
//	}
//	for (int i = 1; i <= N; i ++ ){
//		cout << i << ":\n";
//		for (int x : g[i]) {
//			cout << x << ' ';
//		}
//		cout << '\n';
//	} 
	int now = N;
	for (int i = 1; i <= Q; i ++ ) {
		int id = upper_bound(c + 1, c + 1 + N, a[i].x) - c;
		bool f = 0;
		if (c[id] > a[i].x) {
			for (int j = now; j >= id; j -- ) {
				for (int v : g[b[j].id]) {
					upd (1, 1, N, lpos[v], 0);
	//				cout << "del:" << v << ' ' << lpos[v] << '\n';
				}
				upd (1, 1, N, lpos[b[j].id], 1);
	//			cout << "ins:" << b[j].id << ' ' << lpos[b[j].id] << '\n';
				f = 1;
			}
			if (f) now = id - 1;
		} 
//		for (int j = 1; j <= N; j ++ ) {
//			cout << query (1, 1, N, j, j) << " \n"[i == N]; 
//		}
		res[a[i].id] = query (1, 1, N, a[i].l, a[i].r);
	}
	for (int i = 1; i <= Q; i ++ ) {
		cout << res[i] << '\n';
	}
}

signed main() {
  int T = 1;
  while (T--)solve();
  return 0;
}