4298. 三元上升子序列

【题目描述】

Erwin 最近对一种叫 thair 的东西巨感兴趣。。。

在含有 $n$ 个整数的序列 $a_1,a_2,\cdots,a_n$ 中，三个数被称作 thair 当且仅当 $i<j<k$ 且 $a_i<a_j<a_k$。

求一个序列中 thair 的个数。

【输入格式】

开始一行一个正整数 $n$,

以后一行 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

【输出格式】

一行一个整数表示 thair 的个数。

【样例输入#1】

4
2 1 3 4

【样例输出#1】

2

【样例输入#2】

5
1 2 2 3 4

【样例输出#2】

7

【样例说明】

样例 2 解释

$7$ 个 thair 分别是:

$1, 2, 3$

$1 ,2, 4$

$1, 2, 3$

$1, 2, 4$

$1, 3, 4$

$2, 3, 4$

$2, 3, 4$

【数据规模与约定】

对于 $30\%$ 的数据 保证 $n \le 100$；

对于 $60\%$ 的数据 保证 $n \le 2000$；

对于 $100\%$ 的数据 保证 $1\le n \le 1\times 10^5$，$1 \le a_i \le 10^5$。