题目描述

有 $N$ 名学生，学号从 $0$ 到 $N-1$，每名学生有一个身高值。老师依次点名 $M$ 名学生加入队列，规则如下：

• 每名被点到的学生先站到队列末尾（第一个入队的学生直接站好即可）。
• 随后，队列中的所有学生需要按照身高从低到高重新排列。身高相同的同学之间顺序可以任意。

同学们通过两两交换位置来完成排序。每次操作可以选择队列中的两名同学交换位置。

例如队列中学号依次为 $10, 17, 3, 25$，让 $3$ 号和 $10$ 号交换后变为 $3, 17, 10, 25$，这就是一次交换。

请计算：在每次点名后，在已有队列的基础上，最少需要几次交换才能完成按身高排序。

输入格式

第一行一个整数 $N$，表示学生总数。

第二行 $N$ 个空格分隔的正整数，依次表示学号 $0, 1, \ldots, N-1$ 对应的身高（值不超过 $2147483647$）。

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

接下来 $M$ 行，每行一个整数 $x$（$0 \le x \lt 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 \le M \le N \le 2000$。对于 $50\%$ 的测试点，保证所有学生的身高互不相同。