区间阈值计数

题目描述

给定长度为 n 的序列 a。有 q 次询问，每次给出 l,r,x，要求统计区间 [l,r] 中有多少个数不超过 x。

输入格式

第一行两个整数 n,q。第二行 n 个整数 a_i。接下来 q 行，每行三个整数 l,r,x。

输出格式

对每次询问输出一行一个整数，表示满足条件的元素个数。

数据范围

1 ≤ n,q ≤ 2 imes 10^5，1 ≤ a_i,x ≤ 10^9，1 ≤ l ≤ r ≤ n。

样例输入

5 3
3 1 4 1 5
1 5 3
2 4 1
3 5 4

样例输出

3
2
2

第一行两个整数 n,q。第二行 n 个整数 a_i。接下来 q 行，每行三个整数 l,r,x。

对每次询问输出一行一个整数，表示满足条件的元素个数。

1 ≤ n,q ≤ 2 imes 10^5，1 ≤ a_i,x ≤ 10^9，1 ≤ l ≤ r ≤ n。