题目描述
考虑一个由自然数组成的序列：
x1,x2,…,xk
以及一个分数 c。若某个数 xi 小于整个序列平均数的 c 倍，则称 xi 是“忧伤的（sad）”。形式化地，若
xi<c⋅kx1+x2+⋯+xk,
则称 xi 为“忧伤的”。
为了让序列中不再存在“忧伤的”数，允许执行如下操作：
但遗憾的是，执行一次这样的操作后，不仅被增加的这个数仍然可能是“忧伤的”，甚至一些原本不是“忧伤的”数也可能变成“忧伤的”。
我们定义：
t(c,{x1,x2,…,xk})
为使得序列中不存在“忧伤的”数所需的最少操作次数。
给定自然数 n,q，数组
a1,a2,…,an,
以及 q 个三元组 (l,r,c)。对于每个询问，请求出：
t(c,{al,al+1,…,ar}).
请特别注意内存限制。
输入格式
第一行输入两个整数 n 和 q。
第二行输入 n 个自然数：
a1,a2,…,an.
接下来 q 行，每行输入三个整数 l,r,p，其中
c=1000p.
输出格式
对于每个询问，输出一行对应的答案。
数据范围
- 1≤n,q≤500000
- 1≤l≤r≤n
- 1≤ai≤1000000000
- 0≤p≤1000
子任务
| 子任务 |
分值 |
额外限制 |
| 1 |
5 |
n,q,ai≤100 |
| 2 |
10 |
n,q≤5000 |
| 3 |
25 |
n,q≤100000 |
| 4 |
n≤100000 |
| 5 |
35 |
无 |
只有在正确通过该子任务的全部测试后，才能获得该子任务的分数。
样例
输入
3 2
3 2 1
1 3 900
3 3 1000
输出
3
0
