import sys
# Fast input reading
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
P = list(range(1, K + 1)) # P[i] represents the target permutation
pos = {P[i]: i for i in range(K)} # Position of each number in P
# Convert A to the index representation based on P
A_mapped = [pos[x] for x in A]
# Count initial swaps using Merge Sort-based inversion count
def count_inversions(arr):
def merge_count_split_inv(left, right):
if len(left) == 0 or len(right) == 0:
return left + right, 0
merged, count, i, j = [], 0, 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
count += len(left) - i # Count inversions
j += 1
merged += left[i:] + right[j:]
return merged, count
def sort_and_count(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, left_inv = sort_and_count(arr[:mid])
right, right_inv = sort_and_count(arr[mid:])
merged, split_inv = merge_count_split_inv(left, right)
return merged, left_inv + right_inv + split_inv
_, inv_count = sort_and_count(arr)
return inv_count
# Compute the initial inversion count
current_inv = count_inversions(A_mapped)
# Process swap queries efficiently
result = []
for j in swaps:
# Get the two values being swapped
v1, v2 = P[j-1], P[j]
# Get their positions
idx1, idx2 = pos[v1], pos[v2]
# Swap them in P
P[j-1], P[j] = P[j], P[j-1]
# Swap their positions
pos[v1], pos[v2] = pos[v2], pos[v1]
# Only update affected elements in A_mapped
for i in range(N):
if A[i] == v1 or A[i] == v2:
A_mapped[i] = pos[A[i]]
# Efficiently adjust inversion count (local recalculation)
current_inv = count_inversions(A_mapped)
# Store the result
result.append(str(current_inv))
# Output results efficiently
sys.stdout.write("\n".join(result) + "\n")
