AT_arc181_d [ARC181D] Prefix Bubble Sort

[problemUrl]: https://atcoder.jp/contests/arc181/tasks/arc181_d $ (1,2,\dots,N) $ の順列 $ P=(P_1,P_2,\dots,P_N) $ が与えられます。 この順列に対して以下のような操作 $ k\ (k=2,3,\dots,N) $ を考えます。 - 操作 $ k $ : $ i=1,2,\dots,k-1 $ の順に「 $ P_i\ >\ P_{i+1} $ ならば $ P $ の $ i,i+1 $ 項目の値を入れ替える」を行う。 長さ $ M $ の**広義単調増加**数列 $ A=(A_1,A_2\dots,A_M)\ (2\ \leq\ A_i\ \leq\ N) $ が与えられます。 各 $ i=1,2,\dots,M $ について、 $ P $ に対し操作 $ A_1,A_2,\dots,A_i $ をこの順に適用した後の $ P $ の転倒数を求めてください。 数列の転倒数とは 長さ $ n $ の数列 $ x=(x_1,x_2,\dots,x_n) $ の転倒数とは、 整数の組 $ (i,j)\ (1\leq\ i\ であって、\ x_i\ >\ x_j $ を満たすものの個数です。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ P_1 $ $ P_2 $ $ \dots $ $ P_N $ $ M $ $ A_1 $ $ A_2 $ $ \dots $ $ A_M $

$ M $ 行出力してください。 $ k $ 行目には $ i=k $ に対する問題の答えを出力してください。

### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ M\ \leq\ 2\ \times\ 10^5 $ - $ 2\ \leq\ A_i\ \leq\ N $ - $ P $ は $ (1,2,\dots,N) $ の順列 - $ i=1,2,\dots,M-1 $ に対して $ A_i\ \leq\ A_{i+1} $ が成り立つ - 入力される値はすべて整数 ### Sample Explanation 1 まず最初に操作 $ 4 $ が行われます。操作 $ 4 $ の過程で $ P $ は $ (3,2,4,1,6,5)\rightarrow\ (2,3,4,1,6,5)\rightarrow\ (2,3,4,1,6,5)\ \rightarrow\ (2,3,1,4,6,5) $ と変化します。操作 $ 4 $ が行われた後の $ P $ の転倒数は $ 3 $ です。 続けて操作 $ 6 $ が行われると $ P $ は最終的に $ (2,1,3,4,5,6) $ に変化し、転倒数は $ 1 $ になります。