题目描述

你有一个长度为 $n$ 的序列，每项都是不超过 $k$ 的正整数。

你的朋友发明了一个排序算法，可以根据一个 $1 \sim k$ 的排列对序列进行排序，排序后序列中任意两个不相等的数的相对位置与排列中的相对位置相同。他的算法只使用了邻项交换的操作，且总是保证操作次数最少。为了方便描述，他将这个 $1 \sim k$ 的排列称为目标排列。

例如，序列为 $[1, 4, 2, 1, 2]$，目标排列为 $[4, 1, 2, 3]$，排序后为 $[4, 1, 1, 2, 2]$。

你对你朋友的排序算法在目标排列不同时执行 swap 的次数很感兴趣。为了研究其中的规律，你一开始将目标排列设置为 $1 \sim k$，并以此进行 $q$ 次操作，每次操作交换目标排列中相邻的两个数的位置。每次交换后，你想知道如果用他的排序算法对原序列进行排序会执行 swap 的次数。

输入格式

第一行，三个整数 $n, k, q$。

第二行，$n$ 个正整数 $a_1, a_2, \cdots, a_n$，表示原序列。

接下来 $q$ 行，每行一个正整数 $b$，表示交换目标排列中的第 $b$ 和第 $b + 1$ 个数。

输出格式

对于每次询问，输出一个整数，表示所求的值。

5 4 3
1 4 2 1 2
3
2
1

4
2
2

提示

数据范围

由于官方数据包过大，本题只节选了官方数据的 $\frac{20}{27}$。

对于 $\frac{4}{27}$ 的数据，$1 \leq n, q \leq 5 \times 10^3$；

对于另外 $\frac{4}{27}$ 的数据，$1 \leq q \leq 100$；

对于另外 $\frac{7}{54}$ 的数据，$1 \leq k \leq 500$；

对于 $100\%$ 的数据，$1 \leq n, k \leq 10^5$，$1 \leq q \leq 10^6$，$1 \leq a_i \leq k$，$1 \leq b < k$。

题目来源

CCO2021 D1T1