题目描述

莫图努伊岛上的公鸡数量增长了，现在嘿嘿公鸡和它的同类们正在寻找食物。

众所周知，岛上的公鸡并不以智慧和机智著称，因此它们以石头为食，每块石头的特征是其美味度 $k_i$。

现在有 $n$ 只公鸡站在一条直线上，这条直线上有 $m$ 块石头。它们按照以下算法行动：确定美味度最高的石头，然后沿直线走向它。最先到达的公鸡会立即吃掉最美味的石头，然后所有公鸡开始走向下一个美味度最高的石头。如果多只公鸡同时到达同一块石头，那么编号较小的公鸡吃掉该石头。

请为每块石头确定，哪只公鸡会吃掉它。

输入格式

第一行输入一个整数 $n$——公鸡的数量（$1 \le n \le 10^5$）。

第二行列出 $n$ 个整数 $a_i$——公鸡的坐标（$0 \le a_i \le 10^9$）。

第三行输入一个整数 $m$——石头的数量（$1 \le m \le 10^5$）。

接下来 $m$ 行每行列出两个整数 $k_i$ 和 $b_i$——分别表示石头的美味度和坐标（$1 \le k_i \le 10^9$；$0 \le b_i \le 10^9$）。

保证所有石头的坐标互不相同，所有石头的美味度也互不相同。

输出格式

输出 $m$ 行，每行一个数字——表示吃掉对应石头的公鸡编号。

2
3 10
3
70 5
10 6
100 7

1
2
2

1
5
4
10 11
5 9
6 10
4 100

1
1
1
1