题目描述

你有一个长度为 $n$ 的序列 $a$，有 $m$ 次查询，每次查询一个区间中能选出不重叠的子区间数量最大值，使每个子区间都存在出现次数大于等于 $k$ 的数。

输入格式

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

第二行 $n$ 个正整数 $a_1, a_2, \dots, a_n$。

接下来 $m$ 行每行三个正整数 $l, r, k$ 表示一个询问。

输出格式

输出 $m$ 行，每行包含一个整数，表示询问的答案。

样例输入 #1

10 10
3 2 4 4 3 4 2 3 2 3 
1 7 7
3 10 1
1 2 5
7 9 3
2 6 2
7 9 1
3 8 1
2 9 2
4 5 10
8 9 9

样例输出 #1

0
8
0
0
1
3
6
2
0
0

说明/提示

对于所有数据，满足 $1\le n,m\le 3\times10^5$，$1\le a_i \le n$。