N. 什么是缘分呢

Type: Default

1000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

人的一生会和很多人相遇。每个人都拥有独属于自己的缘分值，代表相遇的珍贵程度。我们将一生中遇到的所有人，按照相遇的先后顺序排成一个序列。生活总有遗憾：很多时候，先遇见的人缘分更深，后遇见的人缘分更浅，却终究擦肩而过、顺序颠倒。

给定长度为 $n$ 的序列 $a$ ，代表你依次相遇的所有人的缘分值。对于一组下标 $i,j$ ，若满足： $i < j,\ a_i > a_j$ 则称这是一次错位相遇。请你求出整段人生相遇记录中，一共存在多少组错位相遇。

第一行一个整数 $n$ ，表示相遇的总人数。第二行 $n$ 个整数，表示按相遇顺序记录的所有人的缘分值。

输出一个整数，表示错位相遇的总数量。样例输入

5
3 1 4 2 5

样例输出

三组错位相遇分别为： $(3,1),(3,2),(4,2)$ ，总计三组。

对于 100% 的数据： $1 \le n \le 10^5,\ |a_i| \le 10^9$ 。