编程题：小杨的列队问题


**时间限制：1.0s**

**内存限制：128.0MB**

【问题描述】
小杨的班级里共有N 名同学，学号从0 至N-1。

某节课上，老师要求同学们进行列队。具体来说，老师会依次点名M 名同学，让他们加入

队伍。每名新入队的同学需要先站到队伍末尾（刚开始队伍里一个人都没有，所以第一个

入队的同学只需要站好即可），随后，整个队伍中的所有同学需要按身高从低到高重新排

序（身高相同的同学之间的顺序任意）。

排队很容易，但重新排序难倒了同学们。稍加讨论后，他们发现可以通过交换位置的方法

来实现排序。具体来说，他们可以让队伍中的两名同学交换位置，这样整个队伍的顺序就

会发生变化，多经过这样的几次交换后，队伍的顺序就可以排号。

*例如：队伍中有4 名同学，学号依次为10, 17, 3, 25，我们可以令3 号同学和 10 号

同学交换位置，则交换后的队伍顺序变为3, 17, 10, 25，这就是一次交换位置。

聪明的小杨想要知道：在老师每次点名一位新同学加入队伍后，在原有队伍的基础上，同

学们最少要进行几次**交换位置**，才能完成老师按身高排序的要求。

【输入描述】

第一行一个整数N，表示同学的数量。

第二行N 个用空格隔开的正整数，依次表示学号为0, 1, ……, N-1 的同学的身高（不超

过 2,147,483,647）。

第三行一个整数M，表示老师点名的数量。

接下来M 行，依次描述M 次点名：每行一个整数x（0<=x<N），表示要求学号为 x 的同

学加入队伍。保证该名同学此前不在队伍中。

对于所有的测试点，保证1<=M<=N<=2,000。对于50% 的测试点，保证所有同学的身高互

不相同。

【输出描述】

输出M 行，依次表示对于每次点名，同学们最少要进行几次**交换位置**，才能完成按身

高排序的要求。

【特别提醒】
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不

要在输入、输出中附带任何提示信息。

【样例输入 1】

5
170 165 168 160 175
4
0
3
2
1

【样例输出 1】

0
1
1
2

【样例解释 1】

初始时队伍为空，身高为170 的0 号同学加入队伍，不需要任何交换位置。

接着，身高为160 的3 号同学加入队伍的末尾，此时两位同学需要进行依次交换位置，才

能保证身高更矮的3 号同学排在身高更高的0 号同学前面。

接着，身高为168 的2 号同学加入队伍的末尾，此时队伍中的同学学号（身高）依次为

3(160), 0(170), 2(168)，此时2 号同学可以和0 号同学进行一次交换位置，即可完成

排序要求。

接着，身高为165 的1 号同学加入队伍的末尾，此时队伍中的同学学号（身高）依次为

3(160), 2(168), 0(170), 1(165)，此时可以令1 号同学和2 号同学进行一次交换位

置，使队伍变为 3(160), 1(165), 0(170), 2(168)；随后再令0 号同学和2 号同学

进行一次交换位置，使队伍变为 3(160), 1(165), 2(168), 0(170)，即可完成排序要

求。

【样例输入 2】
4
20 20 20 10
4
0
1
2
3

【样例输出 2】

0
0
0
1

【样例解释 2】

前三位加入队伍的同学（0, 1, 2 号同学）身高都相同，不需要进行任何交换位置。最后
加入队伍的3 号同学身高最矮，需要和队头的0 号同学交换位置，方可完成排序要求。