前缀冒泡排序

时间限制：2s
空间限制：1024MB

题目描述

给定 $(1,2,\ldots,N)$ 的一个排列 $P=(P_1,P_2,\ldots,P_N)$。对每个 $k\in[2,N]$，定义操作 $k$：依次令 $i=1,2,\ldots,k-1$，若当前 $P_i>P_{i+1}$，就交换这两个相邻元素。

另给定长度为 $M$ 的非降序列 $A=(A_1,A_2,\ldots,A_M)$，其中 $2\le A_i\le N$。对每个 $i=1,2,\ldots,M$，求依次执行操作 $A_1,A_2,\ldots,A_i$ 后排列 $P$ 的逆序对数。序列 $x$ 的逆序对是满足 $1\le p<q\le\vert x\vert$ 且 $x_p>x_q$ 的下标对 $(p,q)$。

输入格式

N
P_1 P_2 ... P_N
M
A_1 A_2 ... A_M

输出格式

输出 $M$ 行，第 $i$ 行表示执行前 $i$ 个操作后的逆序对数。

样例输入 1

6
3 2 4 1 6 5
2
4 6

样例输出 1

3
1

样例输入 2

20
12 14 16 8 7 15 19 6 18 5 13 9 10 17 4 1 11 20 2 3
15
3 4 6 8 8 9 10 12 13 15 18 18 19 19 20

样例输出 2

117
116
113
110
108
105
103
99
94
87
79
72
65
58
51

数据范围

• $2\le N\le2\times10^5$；
• $1\le M\le2\times10^5$；
• $P$ 是 $(1,2,\ldots,N)$ 的排列；
• $2\le A_i\le N$，且 $A_i\le A_{i+1}$。