题目描述

$Bob$ 最近学习了逆序对，对于给定序列 $A[]$ 逆序对定义为 $i<j,A_i>A_j$ , 他觉得逆序对太简单了，于是老师提高了难度，请你帮忙解决。

对于给定长度为 $n$ 的序列 $A[]$，进行 $m$ 询问: 每次给定一个数 $h$ , $Bob$ 需要将序列中小于 $h$ 的数临时变为 $h$ , 然后回答整个序列中逆序对总个数。（注意每次询问结束，序列恢复为原始状态）

输入格式

第一行一个整数 $n$ ,表示序列长度

接下来一行 $n$ 个整数，表示序列 $A[]$

接下来一行一个整数 $m$ ,询问次数

接下来 $m$ 行，每行一个整数 $h$ ,含义如题。

输出格式

$m$ 行，每行一个整数，对于每一个 $h$ ,按照题目要求输出逆序对个数。

5
2 5 3 3 1
3
2
4
5

5
3
0

样例1解释

第 $1$ 次询问，$h=2$，序列变为： 2 5 3 3 2, 逆序对个数为 $5$

第 $2$ 次询问，$h=3$，序列变为： 2 5 3 3 3, 逆序对个数为 $3$

第 $3$ 次询问，$h=5$，序列变为： 5 5 5 5 5, 逆序对个数为 $0$

5
10 8 5 10 1
5
5
3
7
10
2

6
7
6
0
7

下发文件：down.zip

数据规模与约定

$subtask1$: $2\le n \le 10^3$,$1 \le m\le 10^3$, $1\le a_i ,h \le 10^3$ , $20$ 分

$subtask2$: $2\le n \le 10^3$,$1 \le m\le 10^3$, $1\le a_i,h\le 10^9$ , $10$ 分

$subtask3$: $2\le n \le 10^5$,$1 \le m\le 10^5$, $1\le a_i,h\le 10^5$ , $60$ 分

$subtask4$: $2\le n \le 10^5$,$1 \le m\le 10^5$, $1\le a_i,h\le 10^9$ , $10$ 分