2852. [NOIP模拟] 蚂蚁搬家

【题目描述】

很久很久以前，有很多蚂蚁部落共同生活在一片祥和的村庄里。但在某一天，村庄里突然出现了一只食蚁兽，蚂蚁们为了保全性命而决定搬家。

然而这个村庄四面环山，想要离开这个村庄必须要从地洞里离开，村子里一共有2n个地洞，分布在山的左右，一边n个。左边的任意一个地洞都可以通到右边n个地洞中的任意的一个，如图所示（两侧地洞从上至下编号为1到n）。

对于右边的第i个出口，附近有数量为wi的食物。

现在前后依次来了q个蚂蚁部落，第i个部落有ai只蚂蚁，它们会从左边第bi个地洞离开，并且选择一个右侧的出口，出口的食物必须大于等于ai，如果有多个满足要求的出口，则选择距离bi最近的（假设蚂蚁从右边的编号为k的地洞出来，那么距离定义为∣k−bi|）。如果有多个洞口符合要求，选择编号最小的出口离开，并且占据这个出口数量为ai的食物，当前洞口的食物数量减少ai。

请输出每群蚂蚁会选择哪个出口，如果没有符合要求的出口，输出-1，并且忽略这群蚂蚁。

【输入格式】

第一行两个整数n和q。

接下来n行，每行一个整数wi，表示右方第i个洞口的食物数量。

接下来q行，每行两个整数ai和bi，表示蚂蚁数量和它们离开的洞口。

【输出格式】

一共q行，每行一个整数，表示第i群蚂蚁会选择哪个出口。

【样例输入】

5 5
9 8 6 10 5
4 5
2 5
8 1
9 3
3 1

【样例输出】

5
4
1
-1
2

【提示】

对于30%的数据：0≤n,q≤3000。

对于60%的数据：0≤n,q≤100000。

对于另外20%的数据保证：ai=1。

对于100%的数据：0≤n,q≤500000，ai,wi≤10^9，bi≤n。

【来源】

NOIP 2017 模拟赛