#2974. stong9070奇遇记之请求

stong9070奇遇记之请求

背景

“stong9070 has arrived!”

大杀四方的 冷亦萧 很快就吓退了敌军,雄赳赳气昂昂地回到了总部。

双枪经过血战已经有了些许磨损,于是 冷亦萧 来到了武器库,准备向特种管理员 stong9070 讨个武器。

不巧的是,stong9070 的仓库前不久刚受到了核弹的冲击,枪支全部散落在了地上。他答应 冷亦萧,如果他帮他整理好了武器,并且能够帮他完美处理若干次寻找合适枪支的任务,他就帮 冷亦萧 找一把趁手的特种武器。

题目描述

stong9070 的仓库内一共有 nn 把武器,第 ii 把武器的战斗力为 aia_i,编号为 ii

冷亦萧 的第一个任务是将这 nn 把武器的战斗力按照升序排序,并输出排好序之后的武器编号,如果两把武器的战力相同则编号较小的在前。

第二个任务是处理 qq 次询问。对于每次询问,stong9070 会给出一个战斗力 xx,冷亦萧 需要快速地找出 nn 个武器中,战斗力大于等于 xx 的第一把(升序排序后)武器,并输出其编号。

你能帮 冷亦萧 完成这两个任务,获得特种枪支吗?

输入格式

第一行两个正整数 n,qn,q,表示武器个数和询问次数。

第二行 nn 个正整数 aia_i,表示每个武器的战斗力。

33 行到第 q+2q+2 行,每行一个整数 xx 表示一次询问。

输出格式

第一行 nn 个正整数表示武器按照战斗力升序排序后的编号。

22 行到第 q+1q+1 行每行一个整数表示寻找到的武器的编号。若对于某次询问无法找到任何合适的武器,则输出 -1

样例

5 4
2 4 8 2 1
2
5
0
9
5 1 4 2 3
1
3
5
-1

样例解释

五件武器排序后的战斗值为 1,2,2,4,81,2,2,4,8,对应的编号为 5,1,4,2,35,1,4,2,3

数据范围

本题采用子任务评分,但不采用捆绑测试

子任务序号 说明 分值
#1\#1 n,q103n,q\le10^3 2020
#2\#2 所有的 aia_i 都相等
#3\#3 xmaxaix\le \max a_i 3030
#4\#4 无特殊要求
#510\#5-10 5050

其中 maxai\max a_i 表示 aia_i 中最大的那个。

对于 100%100\% 的数据,1n,q1051\le n,q\le 10^51ai,x1081\le a_i,x\le 10^8.