You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

该题并不根据实际情况改编，请大家认真上课。

kuro沉迷于世界巧克力包装竞赛(International Chocolate Package Contest，简称ICPC)的训练中，每天都不想上课，尤其是巧克力结构(Chocolate Structure，简称CS)相关的课程，所以他决定开始自学！

但不幸的是，自学是有概率被抓到的，kuro不想被抓到，所以他进行了一系列调研，得到了每一门课程的自学危险度，他希望能专注训练，所以他打算自学的课为连续的。

kuro一共有$n$节课，kuro希望在自学的课的总危险度不大于被抓阈值的情况下，尽可能多自学。

但他的课程实在太多了，经过计算，得到了$q$个从第$k$节课开始自学的"被抓阈值"$m$，希望你能告诉他从已知的每一个开始时间$k$开始自学，最多能自学多少节。

Input Format

第一行包含两个整数$n (1 \leq n \leq 10^6)$和$q (1 \leq q \leq 10^5)$表示课程数量和询问数量

接下来的一行包含$n$个整数$a_i(1 \leq i \leq n)$$(1 \leq a_i \leq 10^9)$，表示每节课的自学危险度。

接下来的$q$行，每行包含两个整数$k$,$m$，表示询问从第$k(1 \leq k \leq n)$节课开始自学，被抓阈值为$m(1 \leq m \leq 10^{18})$时最多能自学的节数。

Output Format

对于每个查询，输出一个整数，表示从第$k$节课开始最多能逃的连续课数。

Sample

输入 #1

5 4
3 2 5 1 4
1 7
2 7
4 100
3 1

输出 #1

2
2
2
0

样例解释

• 对于第一组查询，从第 1 节课开始，最多能自学 2 节课（在第 1 和 2 节自学，危险度总和为 ( 3 + 2 = 5 )）。
• 对于第二组查询，从第 2 节课开始，最多能自学 2 节课（在第 2 和 3 节自学，危险度总和为 ( 2 + 5 = 7 )）。
• 对于第三组查询，从第 4 节课开始，最多能自学 2 节课（在第 4 和 5 节自学，危险度总和为 ( 1 + 4 = 5 )）。
• 对于第四组查询，从第 3 节课开始，没办法自学（第三节课的危险度为5，已经大于被抓阈值）。

Hint

p.s.该题目题面的第一个版本是将当前版本的所有自学替换成逃课