问题 2354 --整理试卷

2354: 整理试卷

时间限制: 1 Sec  内存限制: 32 MB
提交: 8  解决: 8
[提交][状态][讨论版][命题人:]

题目描述

小明是班里的C语言课代表,有一天他被C语言老师叫去把期中考试的试卷从旧办公室搬到新办公室去。老师之前已经按照成绩从低到高把试卷排好了,并且嘱咐小明搬的时候不要把试卷的顺序弄乱了。
但巧的是,小明在搬着试卷走的过程中迎面走来一漂亮妹子,于是小明本能的目送美女走过,然后撞到了一个女汉子……就这样,试卷撒了一地,于是乎小明马上捡完试卷堆成一摞,但是试卷的顺序都乱掉了。
小明是刚进ACM校队的新人,他想趁此机会考考你,问你任意交换相邻的两张试卷,使得最后整个试卷序列按照成绩从低到高排好,最少需要交换多少次?

输入

输入包含多组测试数据。
每组第一行输入一个整数n(0<=n<=1000),表示试卷的张数,当n=0时,输入结束。
接下来一行输入n个互不相同的非负整数,每个整数最大不超过32位int型的范围。

输出

对于每组输入,输出使得最后整个试卷序列按照成绩从低到高排好的最少交换次数。

样例输入

5
4 2 1 7 5
3
1 2 3
8
9 8 7 6 5 4 3 2
0

样例输出

4
0
28

来源

 

[提交][状态]