class FenwickTree:
def __init__(self, size):
self.size = size
self.tree = [0] * (size + 1)
def add(self, index, value):
while index <= self.size:
self.tree[index] += value
index += index & -index
def sum(self, index):
total = 0
while index > 0:
total += self.tree[index]
index -= index & -index
return total
def range_sum(self, left, right):
return self.sum(right) - self.sum(left - 1)
def count_inversions(arr, K):
# Map values to their positions in P
ft = FenwickTree(K)
inv_count = 0
for i in range(len(arr)):
inv_count += ft.range_sum(arr[i] + 1, K)
ft.add(arr[i], 1)
return inv_count
def swap_and_update(swaps, pos_map, A, K):
inv_count = count_inversions([pos_map[x] for x in A], K)
result = []
for j in swaps:
val1, val2 = pos_map[j], pos_map[j + 1]
# Swap in position map
pos_map[j], pos_map[j + 1] = val2, val1
# Adjust inversion count
affected_indices = [x for x in A if x in {j, j + 1}]
new_inversions = count_inversions([pos_map[x] for x in affected_indices], K)
inv_count = new_inversions # Update with new inversions count
result.append(inv_count)
return result
# Reading input
import sys
input = sys.stdin.read
data = input().split()
idx = 0
# Read N, K, Q
N, K, Q = map(int, data[idx:idx+3])
idx += 3
# Read array A
A = list(map(int, data[idx:idx+N]))
idx += N
# Read swap queries
swaps = list(map(int, data[idx:idx+Q]))
# Initial target permutation
pos_map = {i: i - 1 for i in range(1, K + 1)}
# Process swaps and print results
results = swap_and_update(swaps, pos_map, A, K)
sys.stdout.write("\n".join(map(str, results)) + "\n")
