题干：

 

瓦西里喜欢在努力工作后休息，所以你可能经常在附近的一些酒吧见到他。他喜欢 "Beecola"，可以从 n 个不同的商店买到。在第 i 个商店的价格为 xi 元。

瓦西里计划购买他最喜欢的饮料 q 次。在第 i 天他能花 mi 元。他想知道每天他能在多少个商店中买这些饮料。

Input

第一行包含一个整数 n (1 ≤ n ≤ 100 000) — 表示商店的数量。

第二行包含 n 个整数 xi (1 ≤ xi ≤ 100 000) — 表示第 i个商店饮料的价格。

第三行包含一个整数 q (1 ≤ q ≤ 100 000) — 表示天数。

之后 q 行每行包含一个整数 mi (1 ≤ mi ≤ 109) — 第 i 天能花的钱数。

Output

输出 q 个整数。第 i 行表示第 i 天能在多少个商店中购买。

Example

Input

5
3 10 8 6 11
4
1
10
3
11

Output

0
4
1
5

 

题目大意：

   给你一些商店，100000个询问，问每个询问下，大于等于多少个商店的价格？

 

解题报告：

    二分o(q*logn)，可解。因为本题都是整数，所以用lowerbound，upperbound都可以。

 

AC代码1：（lowerbound）

Select Code
#include<bits/stdc++.h>

using namespace std;

int a[100000 + 5];
int main()
{
	int n,q,op,ans;
	cin>>n;
	for(int i = 1;i <=n; i++) {
		scanf("%d",&a[i]);
	}
	scanf("%d",&q);
	sort(a+1,a+n+1);
	while(q--) {
		scanf("%d",&op);
		ans=lower_bound(a+1,a+n+1,op+1)-(a+1);
		printf("%d\n",ans);
	}
	return 0 ;
 }

AC代码2：（upperbound）

#include<bits/stdc++.h>

using namespace std;

int a[100000 + 5];
int b[5]={1,2,2,3,4};
int main()
{
//	cout<< upper_bound(b,b+5,2)-b;
	int n,q,op,ans;
	cin>>n;
	for(int i = 1;i <=n; i++) {
		scanf("%d",&a[i]);
	}
	scanf("%d",&q);
	sort(a+1,a+n+1);
	while(q--) {
		scanf("%d",&op);
		ans=upper_bound(a+1,a+n+1,op)-(a+1);
		printf("%d\n",ans);
	}
	return 0 ;
 }

总结： 无