版权声明

本题版权归 Long Long OJ 所有。

题目背景

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

题目描述

长度为 $n$ 的序列 $a$，需要你支持 $m$ 次以下操作：令 $x$ 为 $a_l, a_{l + 1}, \ldots, a_r$ 中的第 $k$ 小值，求出 $a_l, a_{l + 1}, \ldots, a_r$ 中 $x$ 的出现次数。

输入格式

第一行共两个正整数 $n, m\ (1 \le n, m \le 2 \times 10^5)$，分别表示序列长度和接下来的操作个数。

第二行共 $n$ 个正整数 $a_1, a_2, \ldots, a_n\ (1 \le a_i \le 10^9)$，描述了这个序列。

接下来的 $m$ 行，每行三个正整数 $l, r, k\ (1 \le l \le r \le n, 1 \le k \le r - l + 1)$。

输出格式

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

样例

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

1
1
2