2572. Sort it…

单点时限: 2.0 sec

内存限制: 256 MB

There is a database,partychen want you to sort the database’s data in the order from the least up to the greatest element,then do the query: “Which element is i-th by its value?”- with i being a natural number in a range from 1 to N.

It should be able to process quickly queries like this.

输入格式

The standard input of the problem consists of two parts. At first, a database is written, and then there’s a sequence of queries. The format of database is very simple: in the first line there’s a number $N (1 \leqslant N \leqslant 100000)$, in the next N lines there are numbers of the database one in each line in an arbitrary order. A sequence of queries is written simply as well: in the first line of the sequence a number of queries $K (1 \leqslant K \leqslant 100)$ is written, and in the next $K$ lines there are queries one in each line. The query “Which element is i-th by its value?” is coded by the number i.

输出格式

The output should consist of K lines. In each line there should be an answer to the corresponding query. The answer to the query “i” is an element from the database, which is i-th by its value (in the order from the least up to the greatest element).

样例

Input
5
7
121
123
7
121
3
3
2
5
Output
121
7
123

提示

Hint
After we sort the data we get 7 7 121 121 123,so the postion 3 is 121,the postion 2 is 7 and the position 5 is 123 etc.

1447 人解决,1644 人已尝试。

1733 份提交通过,共有 4756 份提交。

1.0 EMB 奖励。

创建: 15 年,8 月前.

修改: 6 年,2 月前.

最后提交: 1 月,1 周前.

来源: 2009 华东师范大学 研究生复试

题目标签