有一个包含 $N$ 个整数的数组，每个整数的值都在 $1$ 到 $K$ 之间。你的朋友有一个算法，可以根据 $1$ 到 $K$ 这 $K$ 个数字的任意顺序对该数组进行排序。该算法执行一系列交换操作，每次交换数组中两个相邻的元素。该算法执行的交换次数恰好是排序数组所需的最少交换次数。

$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$ ($1 \le K \le N \le 100\,000, 1 \le Q \le 1\,000\,000$)。

第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N$ ($1 \le a_i \le K$)，表示该数组。

接下来的 $Q$ 行，每行包含一个整数 $j$ ($1 \le j \le K - 1$)，表示交换目标排列中索引为 $j$ 和 $j+1$ 的元素的操作。

对于 25 分中的 3 分，满足 $N, Q \le 5\,000$。

对于 25 分中的另外 3 分，满足 $Q \le 100$。

对于 25 分中的另外 5 分，满足 $K \le 500$。

输出格式

对于 $Q$ 次操作中的每一次，输出一行，包含一个整数，即当前目标排列下的答案。

样例

样例输入 1

5 4 3
1 4 2 1 2
3
2
1

样例输出 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]$。