题目描述
小机器人给大家出了一道题:一共有n个从小到大排列的数字,同时小机器写出一个数字x,接下来有m轮问答,每一轮小机器人写出一个数字t,大家需要回答出这n个数中最后一个小于等于x-t的数的位置。请编写一个程序解决小机器人的问题。
可以使用upper_bound函数来找到数组中第一个大于某个值的数的下标pos,pos-1就是数组中最后一个小于等于某个值的数的下标。比如在1 2 2 2 6中找到最后一个小于等于3的数的位置,可以用upper_bound函数先找到第一个大于3的数的位置5,那么4就是最后一个小于等于3的数的位置。
1 <= m,n <=100000
1 <= t <= x <= 100000
输入
共m+2行。
第一行为三个整数n,m,x。
第二行为n个整数,依次表示n个从小到大排列的数字。
接下来m行,每行一个整数t。
输出
m行,每一行表示这个序列中最后一个小于等于当前x-t的数的位置。如果不存在小于等于x-t的数则输出0。
样例输入
5 5 6
1 3 3 5 5
2
6
5
3
4
样例输出
3
0
1
3
1