三元上升子序列 题目描述 Erwin 最近对一种叫 thair 的东西巨感兴趣。。。 在含有 n 个整数的序列 a1,a2,…,an 中，三个数被称作thair当且仅当 i<j<k 且

三元上升子序列

题目描述

SAS100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
Erwin 最近对一种叫 thair 的东西巨感兴趣。。。SAS100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
在含有 n 个整数的序列 a1,a2,…,an 中，三个数被称作thair当且仅当 i<j<k 且 ai<aj<ak。SAS100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
求一个序列中 thair 的个数。

输入

SAS100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
开始一行一个正整数 n,SAS100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
以后一行 n 个整数 a1,a2,…,an。

输出

SAS100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
一行一个整数表示 thair 的个数。

样例输入 

4
2 1 3 4

样例输出

2

提示

SAS100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
样例二：SAS100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入：SAS100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
5SAS100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1 2 2 3 4SAS100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出：SAS100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
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≤100；
• 对于 60% 的数据 保证 n≤2000；
• 对于 100% 的数据 保证 1≤n≤3×10^4，0≤ai<2^63。