题目描述

译自 CCO 2021 Day1「Swap Swap Sort」

给定一个长度为 $N$ 的数组，其中各项均为 $1$ 到 $K$ 内的整数。你的朋友有一个算法，他的算法可以把数组按照任何一种指定顺序排序。这个算法每次只交换数组中的一组相邻元素。它保证能在最小操作次数内完成排序。

所指定的顺序由一个目标排列给出。目标排列是一个 $1$ 到 $K$ 的整数构成的排列，指定顺序就是说最终排序好的数组中数的出现顺序需要和目标排列一致。

例如，数组 [1 4 2 1 2] 按照目标排列 $4, 1, 2, 3$ 的顺序排列就会得到数组 [4 1 1 2 2]。

你想知道给出一些不同的目标排列时，你朋友的算法将进行多少次交换操作。由此，你从一个形如 $1,2,\dots,K$ 的目标排列开始考虑，你接下来对其进行 $Q$ 次操作。每次操作会交换这个目标排列的两个相邻元素。每次操作完后，求出你朋友的算法对这个排列为目标的排序所需次数。这 $Q$ 次操作对目标排列的影响是累加的，但不影响要被排序的原数组。

输入格式

第一行三个整数 $N,K$ 和 $Q$。

接下来一行 $N$ 个整数 $a_1,a_2,\dots,a_N$ 表示要排序的数组。

接下来 $Q$ 行每行一个整数 $j$，表示交换目标排列的第 $j$ 项和第 $j+1$ 项。

输出格式

输出 $Q$ 行每行一个整数，表示对应交换过后的排序算法交换次数。

5 4 3
1 4 2 1 2
3
2
1

4
2
2

目标排列分别是 $1,2,4,3$，然后是 $1,4,2,3$，然后是 $4,1,2,3$。对于最后一个目标排列，算法将 [1 4 2 1 2] 排序成 [4 1 1 2 2]。

数据范围与提示

对于 $100\%$ 的数据，保证 $1\le K\le N\le 10^5$，$1\le Q\le 10^6$，$1\le a_i\le K$，$1\le j\le K-1$。

对于 $12\%$ 的子任务，保证 $N,Q\le 5000$。

对于另外 $12\%$ 的子任务，保证 $Q\le 100$。

对于另外 $20\%$ 的子任务，保证 $K\le 500$。