https://www.luogu.com.cn/problem/P14541 数据加强版

题目描述

聪明兔出门了，再也没有人能限制胖胖龙干饭了！

胖胖龙私藏了 $m$ 份零食，每份零食有一个美味度 $k_i$。胖胖龙想赶在聪明兔回家之前吃完，所以分出了 $n-1$ 个分身（算上自己正好 $n$ 头龙）一起吃。

胖胖龙本来就不聪明，分身之后变得更笨了：所有龙都会沿着直线走向当前剩余美味度最高的食物走去，最先到达的龙会吃掉这份零食，然后所有龙朝着下一个最美味的零食走去直到所有零食都被吃完。如果有好多龙同时到达一份零食面前，那么编号最小的龙会吃掉食物。

请你为每一份零食确定哪头龙会吃掉它。

输入格式

第一行一个整数 $n$，表示恐龙的数量。

第二行列出 $n$ 个整数 $a_i$ 代表每头龙的初始位置坐标。

第三行一个整数 $m$，表示零食的数量。

接下来 $m$ 行，每行两个整数 $k_i,b_i$ 分别表示零食的美味度和坐标。

输出格式

输出 $m$ 行，每行一个整数，表示吃掉对应零食的恐龙编号。

样例1输入

2
3 10
3
70 5
10 6
100 7

样例1输出

1
2
2

样例2输入

1
5
4
10 11
5 9
6 10
4 100

样例2输出

1
1
1
1