2268 - 求逆序对数

题目描述

对于一个长度为 N 的整数序列 A,满足 i < jA_i > A_j 的数对 (i,j) 称为整数序列 A 的一个逆序对;

请求出整数序列 A 的所有逆序对个数。

输入

输入包含多组测试数据,每组测试数据有两行。

第一行为整数 N(1 \le N \le 20000),当输入 0 时结束;

第二行为 N 个整数,表示长为 N 的整数序列。

输出

每组数据对应一行,输出逆序对的个数。

样例

输入

5
1 2 3 4 5
5
5 4 3 2 1
1
1
0

输出

0
10
0
来源

电子学会五级

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 429
通过人数 146
金币数量 2 枚
难度 基础


上一题 下一题