Problem Description

Xiao Yang's class has a total of $N$ students, with student IDs ranging from $0$ to $N-1$. In a certain class, the teacher asked the students to line up. Specifically, the teacher will call up $M$ students in sequence to join the queue. Each new student joining the queue needs to stand at the end of the queue (initially, the queue is empty, so the first student to join only needs to stand in place), and then, all students in the queue need to be reordered from shortest to tallest (students of the same height can be in any order).

Lining up is easy, but reordering stumped the students. After some discussion, they found that they could achieve the sorting by swapping positions. Specifically, they could swap the positions of two students in the queue, which would change the order of the entire queue. After several such swaps, the queue could be sorted.

For example: There are $4$ students in the queue with IDs $10, 17, 3, 25$. We can swap the positions of the student with ID $3$ and the student with ID $10$, resulting in the queue order becoming $3, 17, 10, 25$. This is one swap.

Smart Xiao Yang wants to know: After the teacher calls up a new student to join the queue each time, based on the existing queue, how many minimum swaps are needed for the students to complete the teacher's requirement of sorting by height.

Input Format

The first line contains an integer $N$, representing the number of students.
The second line contains $N$ positive integers separated by spaces, representing the heights of the students with IDs $0, 1, \ldots, N-1$ (not exceeding $2,147,483,647$).
The third line contains an integer $M$, representing the number of times the teacher calls up students.
The next $M$ lines describe the $M$ calls: each line contains an integer $x$ ($0 \le x < N$), representing the ID of the student to be called up. It is guaranteed that this student is not already in the queue.

Output Format

Output $M$ lines, each representing the minimum number of swaps needed for each call to complete the sorting by height.

Sample Input and Output

Sample Input #1

5
170 165 168 160 175
4
0
3
2
1

Sample Output #1

0
1
1
2

Sample Input #2

4
20 20 20 10
4
0
1
2
3

Sample Output #2

0
0
0
1

Notes

For all test cases, it is guaranteed that $1 \le M \le N \le 2000$. For $50\%$ of the test cases, it is guaranteed that all students have different heights.

见题面 Input 部分

见题面 Output 部分