[GESP样题 五级] 小杨的队列

题目描述

小杨的班级里共有 $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 \le x<N$），表示要求学号为 $x$ 的同学加入队伍。保证该名同学此前不在队伍中。

输出格式

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

输入输出样例

5
170 165 168 160 175
4
0
3
2
1

0
1
1
2

4
20 20 20 10
4
0
1
2
3

0
0
0
1

说明/提示

样例 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 解释

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

对于所有的测试点，保证 $1 \le M \le N \le 2000$。对于 $50\%$ 的测试点，保证所有同学的身高互不相同。