题目描述

归并排序是计算机算法中非常经典的基于分治与递归思想的稳定排序算法。该算法的核心思路可以概括为“先分后治”：对于一个无序的完整数据序列，递归地将当前序列从中间位置拆分为左右两个长度尽可能相等的子序列，持续不断地对半拆分，直到所有子序列的长度都变为1。由于单个元素的序列天然是有序序列，此时拆分阶段结束。 完成拆分后，算法进入合并阶段：逐层将两个已经有序的子序列按照数值大小重新合并为一个更大的有序序列。在合并过程中，通过双指针依次比对左右两个有序区间的头部元素，每次取出更小的元素放入临时数组，最终逐级回溯合并，即可得到全局有序的完整数组。相较于冒泡排序、选择排序等暴力枚举排序，归并排序不依赖原始数据的乱序程度，时间复杂度稳定为 $O(n\log n)$，排序效率更高。

在算法定义中，对于数组中的两个元素下标 $i,j$，若满足 $i < j$ 且 $a[i] > a[j]$，则称 $(a[i],a[j])$ 为一组逆序对。

在归并排序的核心合并过程中，存在一个非常重要的算法特性：当我们合并左右两个有序子区间时，如果左侧区间的当前元素大于右侧区间的当前元素，则左侧当前元素及其后方所有未遍历元素，都可以与右侧当前元素构成一组“前大后小”的逆序关系。 根据这一归并分治的核心思想，我们可以在不增加时间复杂度的前提下，在排序合并的同时，高效统计出整个数组中所有的逆序对数量，避免了暴力双重循环枚举的 $O(n^2)$ 低效做法，这也是逆序对问题的最优解法。

现给定一段无序的整数序列，请你利用归并排序分治合并的算法思想，在递归排序的过程中统计该数组中存在的所有逆序对总数，最终输出逆序对的总个数。

输入格式

第一行输入$n$表示数列长度

第二行输入$n$个整数，表示数列中的数

输出格式

一行，表示逆序对个数

输入输出样例

7
9 4 2 7 1 5 8

11

提示

$1 \leq n \leq 10^5$ $对于数列中每一个数$a_i$ $1 \leq a_i \leq 10^8$