Problem Description

You have a sequence of length $n$, where each element is a positive integer not greater than $k$.

Your friend invented a sorting algorithm that can sort the sequence according to a permutation of $1 \sim k$. After sorting, for any two unequal numbers in the sequence, their relative order is the same as their relative order in the permutation. His algorithm only uses adjacent swaps, and it always guarantees the minimum number of operations. For convenience, he calls this permutation of $1 \sim k$ the target permutation.

For example, if the sequence is $[1, 4, 2, 1, 2]$ and the target permutation is $[4, 1, 2, 3]$, then after sorting it becomes $[4, 1, 1, 2, 2]$.

You are very interested in how many swaps your friend’s sorting algorithm performs under different target permutations. To study the pattern, you initially set the target permutation to $1 \sim k$, and then perform $q$ operations on it. In each operation, you swap the positions of two adjacent numbers in the target permutation. After each swap, you want to know how many swaps would be performed if you use his sorting algorithm to sort the original sequence.

Input Format

The first line contains three integers $n, k, q$.

The second line contains $n$ positive integers $a_1, a_2, \cdots, a_n$, representing the original sequence.

The next $q$ lines each contain one positive integer $b$, meaning you swap the $b$-th and the $(b + 1)$-th numbers in the target permutation.

Output Format

For each query, output one integer, representing the required value.

5 4 3
1 4 2 1 2
3
2
1

4
2
2

Hint

Constraints

Because the official data package is too large, this problem only includes $\frac{20}{27}$ of the official testdata.

For $\frac{4}{27}$ of the testdata, $1 \leq n, q \leq 5 \times 10^3$.

For another $\frac{4}{27}$ of the testdata, $1 \leq q \leq 100$.

For another $\frac{7}{54}$ of the testdata, $1 \leq k \leq 500$.

For $100\%$ of the testdata, $1 \leq n, k \leq 10^5$, $1 \leq q \leq 10^6$, $1 \leq a_i \leq k$, $1 \leq b < k$.

Source

CCO2021 D1T1

Translated by ChatGPT 5