You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

​ 小王在上算法设计与分析的课程中首次接触到插入排序，插入排序的基本原理如下：

​ 给定数组$a$，假如$a[1 : i]$有序，考虑将 $a_{i + 1}$ 插入到有序子数组$a[1 : i]$中. 用一个辅助变量记录 $a_{i + 1}$，即 $key = a_{i + 1}$. 接下来，我们从索引 $i$ 逆向遍历到 $1$，如果发现 $a_{j} > key$，则将 $a_{j}$ 移动到 $a_{j + 1}$，直到找到索引$p$，使得 $a_{p} \le key$， 将 $key$ 插入到 $a_{p + 1}$ 中， 即 $a_{p + 1} = key$.显然，$a[1 : i + 1]$ 保持有序。迭代上述过程，直到插入最后一个元素 $a_{n}$， 以使得数组$a$ 有序.

​ 此外，插入排序的C语言代码如下：

//	数组下标从1开始.
void insertionSort(int a[], int n) {
    //	默认 a[1 : 1] 有序
    for (int i = 2; i <= n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 1 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

​ 小王微调上述代码并定义一个$calc(a, n)$ 函数以估算插入排序的计算量，其代码如下：

//	数组下标从1开始.
int calc(int a[], int n) {
    int total = 0;
    //	默认 a[1 : 1] 有序
    for (int i = 2; i <= n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 1 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
            total += 1;
        }
        a[j + 1] = key;
    }
    return total;
}

​ 基于上述灵感，小王决定出一道校赛题，题目描述如下：

​ 给定一个 $n$ 长的整数数组 $a$，要求计算 $calc(a, n)$. 小王认为该问题太简单了(直接套用上述代码即可, hah)，因此决定加大题目难度。

​ 增加 $q$ 次修改操作，每次操作在数组的末尾插入新元素 $x$。注意，修改操作是持久的。 每次修改数组后，计算一次 $calc(a', n')$. ($a'$ 表示修改后的数组， $n'$表示修改后的数组长度)

Input Format

​ 第一行输入一个整数 $n$ ($1 \le n \le 10^{5}$) 和一个正整数 $q$ ($1 \le q \le 10 ^ {5}$)，表示原数组$a$ 的初始长度和修改操作次数。

​ 第二行输入 $n$ 个正整数，表示初始数组的第$i$个元素$a_{i}$.

​ 接下来的第 $3$ 到 $q + 2$ 行，每行输入一个正整数 $x$ ，表示新加入数组 $a$ 的末尾的元素 $x$.

Output Format

​ 输出 $q + 1$行非负整数，其中第一行表示初始数组对应的 $calc(a, n)$， 第 $i + 1$ 行表示第 $i$ 次修改后对应的$calc(a', n')$.

Sample

输入 #1

3 2
2 3 3
1
3

输出 #1

0
3
3

输入 #2

3 1
3 1 3
3

输出 #2

1
1

Hint

确保 $1 \le a_{i} \le 10^9$， 允许数组的元素重复.