3985: 最近平方根2
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：20
解决：10
题目描述
给定 N 个正整数 a[i]，再给出 M 个询问，每个询问包含两个整数 num 和 kind。
你的任务是对于每个 num，输出 a[i]，满足：
1）若 kind=0，则 a[i]*a[i]<=num 且 a[i] 最大；
2）若 kind=1，则 a[i]*a[i]>=num 且 a[i] 最小。
无解输出-1即可。
输入
第一行一个整数 N。
第二行 N 个整数 a[i]。
第三行一个整数 M。
接下来 M 行，每行两个整数 num 和 kind。
输出
对于每个 num 输出一行，表示相应 a[i]，如果 a[i] 不存在，输出 -1。
样例输入 复制
10
401 801 2692 3783 4768 6111 6600 7696 7727 9929
10
43560050 0
22733902 1
160875 1
59706599 0
98585041 0
43560057 1
59706529 0
0 0
98585088 0
59706564 0样例输出 复制
6600
6111
801
7727
9929
7696
7727
-1
9929
7727提示
50%的数据，N,M<=10，所有数据中只有这一部分数据中a[i]是从小到大有序的；
另外30%的数据，N<=5000, M=1；
100%的数据，N<=5000, M<=100000，0<=a[i]<=10000，0<=num<=1000000000。
另外30%的数据，N<=5000, M=1；
100%的数据，N<=5000, M<=100000，0<=a[i]<=10000，0<=num<=1000000000。