3444 - 三元上升子序列
时间限制 : 1 秒
内存限制 : 512 MB
Erwin 最近对一种叫 thair 的东西巨感兴趣。。。
在含有 n 个整数的序列 a_1,a_2,\ldots,a_n 中，三个数被称作thair当且仅当 i
求一个序列中 thair 的个数。
输入
开始一行一个正整数 n,
以后一行 n 个整数 a_1,a_2,\ldots,a_n。
输出
一行一个整数表示 thair 的个数。
样例
输入
4 2 1 3 4
输出
2
输入
5 1 2 2 3 4
输出
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
对于 100\% 的数据 保证 1 \leq n\le3\times10^4，1\le a_i\leq 10^5。