E. 插入排序

内存限制：512 MiB 时间限制：2000 ms 标准输入输出

题目类型：传统评测方式：文本比较

转到题库提交记录返回比赛

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

给定数组，假如有序，考虑将插入到有序子数组中. 用一个辅助变量记录，即 . 接下来，我们从索引逆向遍历到，如果发现，则将移动到，直到找到索引，使得，将插入到中，即 .显然，保持有序。迭代上述过程，直到插入最后一个元素，以使得数组有序.

此外，插入排序的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;
    }
}

小王微调上述代码并定义一个函数以估算插入排序的计算量，其代码如下：

//	数组下标从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;
}

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

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

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

第一行输入一个整数 () 和一个正整数 ()，表示原数组的初始长度和修改操作次数。

第二行输入个正整数，表示初始数组的第个元素.

接下来的第到行，每行输入一个正整数，表示新加入数组的末尾的元素 .

输出行非负整数，其中第一行表示初始数组对应的，第行表示第次修改后对应的.

输入 #1

输出 #1

0
3
3

输入 #2

3 1
3 1 3
3

输出 #2

1
1

确保，允许数组的元素重复.

题目描述

输入格式

输出格式

样例

数据范围与提示