【模板】离线二维数点

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

给定一个长度为 $n$ 的正整数序列 $a$。有 $m$ 次询问，每次给出三个整数 $l,r,x$，求区间 $[l,r]$ 中小于等于 $x$ 的元素个数。

输入格式

第一行输入两个整数 $n,m$。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $m$ 行，每行输入三个整数 $l,r,x$，表示一次询问。

输出格式

对每次询问输出一行一个整数，表示对应答案。

样例输入 1

6 4
1 1 4 5 1 4
1 6 3
1 6 4
1 1 4
1 5 4

样例输出 1

3
5
1
4

数据范围

对于所有数据，$1\le n,m\le2\times10^6$，$1\le a_i,x\le2\times10^6$，$1\le l\le r\le n$。