题目背景

Special for beginners, ^_^

题目描述

给定一个长度为 n 的古老数组 a。

如果存在一对下标 (i, j)，满足：

i < j 且 a[i] > a[j]

那么这对 (i, j) 就叫做一个 逆序对。

请你用递归的方法统计数组中逆序对的总数。

输入格式

第一行一个整数 n

1 ≤ n ≤ 2×10^5

第二行 n 个整数

a[i] ≤ 10^9

输出格式

一个整数, 表示 A 和 B 的和.

样例

5
2 4 1 3 5

3

样例解释

逆序对为：

(2,1) (4,1) (4,3)

共 3 个。