Filtered Records

問題文

正整数 $N$ と長さ $N$ の正整数列 $A, W$ が与えられる。

数列 $B$ に対し、 $1 \le j \lt i$ を満たす $i$ であって $B_j \lt B_i$ を満たすものの個数を $f(B)$ と定義する。 $B$ が空の場合、 $f(B)=0$ である。

$Q$ 個のクエリが与えられる。 $q$ 個目のクエリは整数 $x_q$ として与えられ、その内容は以下のとおりである。

• $W_i\le x_q$ を満たすすべての $i$ について $A_i$ を順序を保ったまま並べた数列を $B$ とする。$f(B)$ を求めよ。

制約

• 入力はすべて整数である。
• $1 \le N,Q \le 2 \times 10^5$
• $1 \le A_i, W_i \le N$ $(1 \le i \le N)$
• $1 \le x_q \le N$ $(1 \le q \le Q)$

入力

入力は以下の形式で標準入力から与えられる。

出力

$Q$ 行出力せよ。$q$ 行目には $q$ 番目のクエリに対する答えを出力せよ。

サンプル

サンプル 1

入力

6 5
3 1 3 2 6 4
4 2 2 3 5 3
1
3
4
5
2

出力

0
3
2
2
2

$X=3$ のとき、$B=(1,3,2,4)$ であり、$f(B)=3$ である。

$X=4$ のとき、$B=(3,1,3,2,4)$ であり、$f(B)=2$ である。