该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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.该题目题面的第一个版本是将当前版本的所有自学替换成逃课