Counting Minimum Adjacent Swaps in Custom Sort

You are given a sequence of length n where each element is a positive integer not exceeding k. You also have a target permutation of the numbers from 1 to k that defines the desired order between different numbers. In the sorted sequence, for any two different numbers x and y, if x appears before y in the target permutation then all occurrences of x must appear before any occurrence of y. The sorting algorithm your friend invented only uses adjacent swaps and always minimizes the number of swaps needed to achieve the order.

For example, consider the sequence [1, 4, 2, 1, 2] and a target permutation P = [4, 1, 2, 3]. After sorting using your friend’s algorithm, the sequence becomes [4, 1, 1, 2, 2] because:

• All occurrences of 4 appear first (since 4 is first in P).
• Next come all occurrences of 1, then 2, and finally 3 (even if 3 does not appear in the sequence).

Initially, the target permutation is set to the identity permutation [1, 2, …, k]. Then you will perform q operations. In each operation, you are given an index p (1-indexed) and you swap the elements at positions p and p + 1 in the target permutation. After each swap, you would like to know the number of adjacent swaps the sorting algorithm would perform on the original sequence if it were sorted using the new target permutation.

The number of swaps equals the number of inversions between pairs of elements (i, j) (i < j) such that if a[i] and a[j] are two different numbers, then the number of a[i] is positioned after a[j] in the current target permutation. Formally, if we denote by pos(x) the position of number x in the target permutation, then the answer equals the sum of f(x,y) for all pairs (x,y) with x ≠ y and pos(x) > pos(y), where f(x,y) is the number of pairs (i, j) such that i < j, a[i] = x and a[j] = y.

inputFormat

The first line contains three integers: n, k and q (n is the length of the sequence, k is the maximum integer value and the range of the target permutation, and q is the number of swap operations).

The second line contains n integers: a[1], a[2], ..., a[n], where each integer is between 1 and k (inclusive).

Each of the next q lines contains one integer p (1 ≤ p < k), indicating that in this operation you swap the elements at positions p and p+1 in the target permutation.

outputFormat

After each swap operation, output one line containing a single integer – the number of adjacent swaps that the sorting algorithm would perform on the original sequence according to the current target permutation.

sample

5 4 3
1 4 2 1 2
3
1
2

4
6
6