問題文
某企业对参加说明会的学生进行了选拔测试。由于举办说明会的场地的最大容量决定了大学生人数,因此测试负责人正在考虑将分界线设定为多少分。
说明选拔方法。
- 当分界线为 x 分时,从取得正积分的学生中 x 选拔所有得分在 分或以上的学生。
- 也就是说,0 分的学生不论场地的最大容纳人数如何都不进行选拔。
你将要进行选拔测试中的 N 会给出学生的积分。 此外,会场的候补有 Q 个。并且,每个会场的最大可容纳学生数是 k_1,k_2,…,k_Q 。 某企业打算在这些会场的候补中选择一个举办说明会。
你的工作是,对于每个会场候补举办说明会的情况,输出最小的分界线。 具体来说,假设在第i (1≦i≦Q) 个会场候补举办说明会时,根据上述方法选拔的学生人数是 k_i 居于以下人数的边界线中 0 输出大于等于此人数且最小的一个。
入力
输入将以以下形式通过标准输入给出。
N s_1 s_2 : s_N Q k_1 k_2 : k_Q
- 1 行是学生人数 N (1≦N≦100,000) 。 来自行
- 2 从第几行开始 N 到第几行为止,为选拔测试中各学生的得分信息。其中 i (1≦i≦N) 行中,i 行是第几名学生的得分 s_i (0≦s_i≦1,000,000) 。 来自行
- 2+N 行中,给出的是会场候选的数量 Q (1≦Q≦100,000) 。 来自行
- 3+N 从第几行开始 Q 行中,给出的是各会场候选的最大容纳人数。其中 i (1≦i≦Q) 行中,i 个会场的最大容纳人数 k_i (0≦k_i≦N) 。 来自行
出力
1 从第几行开始 Q 行中,输出在各会场候选举行说明会的分界线。其中 i (1≦i≦Q) 行中,i 个会场举行说明会时的分界线输出。
入力例1
15 0 0 0 1 1 2 3 4 5 6 6 6 8 9 10 3 0 4 12
出力例1
11 7 0
真是个了不起的案例,但是,1 个会场的最大容纳人数是 0 ,所以不想让任何人通过。为了达到这一点,最小的分界线是 11 分。
2 个会场的最大容纳人数是 4 人,因此必须设置分界线,使得选拔人数不会低于此数。 如果将分界线设置为 6 点时,6 途经人数过多,会场超出最大容量。 如果设置为7 点, 3 只有人可以通过,场地可以容纳,这是最小的边界。
3 个会场的最大容纳人数是 12 但处于临界状态 0 点。因为选择方法 0 学生无法通过,因此他们得到了正分。 12 因为只有人经过它。
入力例2
9 3 3 3 2 2 2 1 1 1 1 4
出力例2
3
入力例3
4 0 0 0 0 1 0
出力例3
0
大家 0 点的情况也是可能的。 在这种情况下,无论你设置哪条边界线,都不会有人通过,所以无论场馆的最大容量是多少,边界线都是 0 点。