A18745.股票购买方案数

时间限制：1000ms
内存限制：512MB

今天是 Alex 的生日，他父亲慷慨地送给了他一大笔现金作为生日礼物。然而，Alex 并不满足于仅仅收下这些钱，而是决定将其投入股市，让钱生钱。

为了在股市中获利，Alex 知道必须以较低的价格购入股票，然后以较高的价格售出。给定一只股票在第 $i$ 天的价格 $a[i]$，现在他想知道在接下来的 $n$ 天内，有多少种方法能让他通过购入再售出股票来赚取利润。正式地，你需要找到满足 $a[i] < a[j] (1 \le i < j \le n)$ 的点对个数。

聪明的 Alex 找到了 Macw，但是 Macw 因为学业繁琐未能解答 Alex 的问题，因此 Macw 找到了你，希望聪明的你能帮帮他。

输入包含两行，
第一行一个整数 $n$，表示给定股票的天数。
第二行包含 $n$ 个整数，每个整数用空格分隔。第 $i$ 个整数表示这只股票第 $i$ 天的单股价格。

输出包含一行一个整数，表示 Alex 购入股票再卖出可以赚钱的方法数。

样例解释：
三种方案分别为：
Alex可以在第二天买入股票，第四天卖出。
Alex可以在第三天买入股票，第四天卖出。
Alex可以在第三天买入股票，第五天卖出。

数据范围：
对于30%的数据，保证 $1 \leq n \leq 10^3$。
对于100%的数据，保证 $1 \leq n \leq 5 \times 10^5$。
对于100%的数据，保证 $1 \leq a[i] \leq 5 \times 10^5$。