问题 1228. -- 逆序数对

1228: 逆序数对

时间限制: 1 Sec  内存限制: 128 MB
提交: 150  解决: 112
[提交][状态][讨论版]

题目描述

输入n个正整数,输出“逆序数对”数目。 
如果两个数中后面的数比前面的数小,则称这两个数为一对“逆序数对”。 
如:3 4 2 1 这四个数中,(3,2)、(3,1)、(4,2)、(4,1)、(2,1)是5对“逆序数对”。 


输入

第一行只有一个正整数:n (1 <= n <= 3 000 ) 
第二行共有n个在闭区间[1,3000]内的正整数,数与数之间用一个空格隔开

输出

第一行只有一个正整数:n个正整数中的“逆序数对”数目 
第二行共有n个按从小到大排列的正整数,数与数之间用一个空格隔开 

样例输入

4
3 4 2 1

样例输出

5
1 2 3 4

提示

来源

[提交][状态]