版权声明

本题版权归 Long Long OJ 所有。

题目背景

球状精灵 pl 在打 ABC 之前启动了 Slay，此时，教练进来了，他只能假装在做数据结构。

题目描述

长度为 $n$ 的序列 $a$，需要你支持 $m$ 次以下操作：令 $x$ 为区间 $l \sim r$ 的 $k$ 小值，求出区间内有多少数等于 $x$。

输入格式

第一行共两个整数 $n, m$，分别表示序列长度和接下来的操作个数。

第二行共 $n$ 个整数 $a_1, a_2, \cdots, a_n$，描述了这个序列。

接下来的 $m$ 行，每行三个整数，格式为 l r k。

输出格式

对于每组询问，输出一行一个整数，表示该组询问的答案。

样例

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

1
1
2

提示

$1\leq n,m\leq2\times10^5$，$1\leq a_i\leq 10^9$，$1\leq l\leq r\leq n$，$1\leq k\leq r-l+1$。