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

题目描述

聪聪在学习生物竞赛，生物竞赛有 $n$ 个知识点，编号为 $1$ ~ $n$，因为有大量需要背的知识点，所以聪聪决定换一种方式来学习，让自己不要太过无聊。

具体地，聪聪会在第 $1$ 天学习知识点 $1$，收获 $a_1$ 的满足度，第 $2$ 天学习知识点 $2$，收获 $a_2$ 的满足度，...，第 $n$ 天学习知识点 $n$，收获 $a_n$ 的满足度，第 $n+1$ 天学习知识点 $1$，收获 $max(0, a_1-1)$ 的满足度，...，第 $2n$ 天学习知识点 $n$，收获 $max(0, a_n-1)$ 的满足度， 第 $2n+1$ 天学习知识点 $1$，收获 $max(0, a_1-2)$ 的满足度，...。

规律是，对于第 $i$ 天，如果 $i \% n=0$，则聪聪会学习第 $n$ 个知识点，收获 $max(0, a_n- \lfloor(i-1/n)\rfloor)$ 的满足度，否则，聪聪会学习第 $i \% n$ 个知识点，收获 $max(0, a_{i\%n}- \lfloor(i-1 / n))$ 的满足度。也就是说，聪聪每学一个知识点一天，下一次学习时候的满足度就会减少 $1$，减到 $0$ 后就不会再收获满足感。

现在，聪聪有 $q$ 个问题，每个问题形如 x t，你需要帮助聪聪计算，假设学到第 $x-1$ 天时，聪聪被老师骂了，之前积累的满足感清零了，那么从第 $x$ 天开始至少到 第几天，才能使得聪聪积累了至少 $t$ 的满足度。

输入格式

第一行输入 $n,q$。

第二行输入一行 $n$ 个数字，表示 $a_1,...,a_n$。

接下来 $q$ 行，每行两个正整数 $x,t$ 表示一次询问。

输出格式

对于每一个询问，输出一个数字表示答案，如果始终无法达成目标，输出 $-1$。

样例1输入

4 3
1 2 3 4
1 10
1 11
1 12

样例1输出

4
6
7

样例1解释

从第一天开始，聪聪连续学习 $4$ 天，可以收获 $1+2+3+4=10$ 的满足度。

但是第 $5$ 天学习知识点 $1$ 的时候，满足感是 $1-1=0$。

第 $6$ 天学习知识点 $2$ 的时候，获得了 $2-1=1$ 的满足感。共 $11$。

第 $7$ 天学习知识点 $3$ 的时候，获得了 $3-1=2$ 的满足感。共 $13$。

数据范围