Logo Daimayuan Online Judge

Home

时间限制:1 s 空间限制:1024 MB

#60. 二分查找2

附加文件 Statistics

给一个序列 $a_1, a_2, \dots, a_n$ 和 $m$ 个询问。

每次询问给出两个数 $l, x$,求最大的 $r (r\leq n)$ 满足 $a_l + a_{l+1} + \dots + a_r \leq x$。

如果不存在这样的 $r$,即 $a_l> x$,输出 $-1$。

输入格式

第一行两个整数 $n, m$。接下来一行 $n$ 个整数,表示 $a_1, a_2, \dots, a_n$。

接下来 $m$ 行,每行两个整数 $l, x$。

输出格式

输出 $m$ 行,每行一个整数表示答案。

样例输入

5 5
1 1 5 3 5
2 8
3 16
3 6
5 4
1 3

样例输出

3
5
3
-1
2

数据规模

对于 $100\%$ 的数据,满足 $1\leq n,m\leq 10^5, 1\leq l\leq n, 1\leq a_i\leq 10^9, 1\leq x\leq 10^{14}$。