该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题目描述】

小灰灰最近特别喜欢研究那些很长很简单的序列，他有一个仅由数字 $\{1,2,3\}$ 构成的长度为 $n$ 的序列，第 $i$ 个元素是 $a_i$。

小灰灰想考考小蓝，于是他询问小蓝，这个序列中逆序对的个数是多少。

如果存在一对元素前面的元素比后面的元素数值大，那么它们就构成一对逆序对。

• 形式化地说，若存在一对有序对 $(i,j)$，满足 $i<j$ 且 $a_i>a_j$，那么这个有序对就是逆序对。

你需要编程求出序列中逆序对的个数。

【输入描述】

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

保证：

• $1\le n\le 10^5$；
• $a_i\in\{1,2,3\}$。

【输出描述】

输出一行一个整数，表示序列中逆序对的个数。

【样例 1】

【样例 1 输入】

3
3 1 2

【样例 1 输出】

2

【样例 1 解释】

序列为 $3,1,2$。

其中 $(1,2)$ 满足 $a_1=3>a_2=1$，构成一对逆序对。

$(1,3)$ 满足 $a_1=3>a_3=2$，也构成一对逆序对。

除此之外没有其它逆序对，所以答案为 $2$。

【样例 2】

【样例 2 输入】

10
2 3 1 2 1 3 2 1 3 1

【样例 2 输出】

19

【样例 2 解释】

统计所有满足前面的数大于后面的数的位置对，一共有 $19$ 对。

【样例 3】

见选手目录下的 Data/sample3.in 和 Data/sample3.ans。

该样例满足 $n\le 1000$。

【样例 4】

见选手目录下的 Data/sample4.in 和 Data/sample4.ans。

该样例满足 $a_i\in\{1,2\}$。

【样例 5】

见选手目录下的 Data/sample5.in 和 Data/sample5.ans。

该样例无特殊性质。

【数据规模与约定】

点击下载本题选手目录