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

校园长跑挑战【题目描述】 学校举办为期 $n$ 天的长跑挑战，第 $i$ 天赛程为 $d_i$。有 $q$ 名选手，每名选手有起跑日 $L$ 和体力值 $S$。选手从第 $L$ 天开始连续奔跑，如果某天跑完后总距离超过 $S$，他就必须停下（即不能跑那一天）。求这名选手最后跑完的是第几天？如果连第 $L$ 天都跑不完，输出 $L-1$。

【输入格式】 第一行包含两个整数 $n, q$ ($1 \le n, q \le 10^5$)，分别表示挑战天数和选手数量。 第二行包含 $n$ 个正整数 $d_i$，表示每天的赛程长度。 接下来 $q$ 行，每行包含两个整数 $L, S$，分别表示选手的起跑日和体力值。

【输出格式】 输出共 $q$ 行，每行一个整数，表示该选手最后完整跑完的比赛日编

样例

5 3
3 2 4 1 5
2 6
1 2
4 10

3
0
5