当前没有测试数据。

题目背景

归并排序是建立在归并操作上的一种有效，稳定的排序算法。

题目描述

请使用归并排序对输入的数组从小到大排序，请求出逆序对的数量。

如果存在正整数 $i, j$ 使得 $1 \leq i < j \leq n$ 而且 $A[i] > A[j]$，则 <$A[i], A[j]$> 这个有序对称为 $A$ 的一个逆序对，也称作逆序数。

输入格式

第 $1$ 行为 整数 $N$ 。

第 $2$ 行为 $N$ 个 空格隔开的整数 。

输出格式

第 $1$ 行为 $N$ 个 已经排序好的整数，用空格隔开 第 $2$ 行为 逆序对的数量

输入输出样例 #1

输入 #1

5
4 2 4 5 1

输出 #1

1 2 4 4 5
5

说明/提示

对于 $20$ 的数据，有 $N\leq10^3$；

对于 $100$ 的数据，有 $N\leq10^5$。