I. Sort it

时间限制:2s

空间限制:256MB

本题分值:400

题目描述

冒泡排序是一种经典的排序算法，冒泡排序（升序排列）的C++代码如下：

template < typename T > void BubbleSort(T a[], int n)
{
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1])
                swap(a[j], a[j + 1]);
        }
}

现有长度为 \(n\) 的整型数组 \(a\)，请问，对于\(x=1,2,...,n\)，如果调用函数

BubbleSort(a, x);

函数过程中将发生几次交换（swap）？（各个询问是独立的）

输入格式

第一行一个正整数 \(n\)，表示数组长度。

第二行 \(n\) 个正整数\(a_i\)，表示这个数组。

输出格式

对于每一个\(x\)，输出对应的答案。

样例输入1

样例输出1

样例1解释

数据范围及限制

\(1\le a_i\le 5*10^5\)

测试点编号	n	测试点分值
1~2	\(1\le n\le 100\)	每个测试点40分
3~4	\(1\le n\le 1000\)	每个测试点60分
5~6	\(1\le n\le 5*10^5\)	每个测试点100分