#2250. 主题公园

主题公园

题目描述

CCF主题公园有 nn 个景点,编号从 11nn。每个景点有一个游玩值,其中第 ii 个景点的游玩值是 aia_i

游客进入CCF主题公园之前需要先通过一个编程水平测试,并得到一个测评值 xx。只有 xaix \ge a_i 时游客才能选择第 ii 个景点游玩;否则(x<aix \lt a_i 时),游客将因为自己的代码水平过弱而被第 ii 个景点拒之门外。

现在有 qq 次询问,每次询问给定一个整数 xx,表示某位游客的编程水平测试成绩,你需要根据他的成绩帮助他确定最多能够选择多少个不同的景点游玩。

输入格式

第一行,一个整数 n(1n100000)n(1 \le n \le 100000),表示CCF主题公园中景点的个数。

第二行,nn 个整数 a1,a2,,an(1ai100000)a_1, a_2, \ldots, a_n(1 \le a_i \le 100000),表示每个景点的游玩值。

第三行,一个整数 q(1q100000)q(1 \le q \le 100000),表示询问次数。

接下来 qq 行,每行包含一个整数 x(1x105)x(1 \le x \le 10^5),表示一次询问。

输出格式

对于每次询问,输出一行,包含一个整数,表示编程水平测试成绩为 xx 的游客最多可以选择多少个不同的景点游玩。

样例输入

5
3 10 8 6 11
4
1
10
3
11

样例输出

0
4
1
5

说明/提示

样例解释

  • 第1次询问:x=1x = 1,游客没有可以选择游玩的景点;
  • 第2次询问:x=10x = 10,游客可以选择第 1,2,3,41, 2, 3, 4 个景点游玩;
  • 第3次询问:x=3x = 3,游客可以选择第 11 个景点游玩;
  • 第4次询问:x=11x = 11,游客可以选择第 1,2,3,4,51, 2, 3, 4, 5 个景点游玩。

数据规模与约定

  • 对于 20%20\% 的数据,n,ai,q,x10n, a_i, q, x \le 10
  • 对于 40%40\% 的数据,n,ai,q,x100n, a_i, q, x \le 100
  • 对于 60%60\% 的数据,n,ai,q,x1000n, a_i, q, x \le 1000
  • 对于 80%80\% 的数据,n,ai,q,x10000n, a_i, q, x \le 10000
  • 对于 100%100\% 的数据,1n,ai,q,x1000001 \le n, a_i, q, x \le 100000