P1637 三元上升子序列
题目描述
Erwin 最近对一种叫做 "thair" 的东西非常感兴趣。
在含有 n 个整数的序列 {a1,a2,…,an} 中,若三个下标 i,j,k 满足 i<j<k 且 ai<aj<ak,则称这三个数构成一个 "thair"。
给定一个序列,请你求出其中 "thair" 的个数。
输入格式
第一行输入一个整数 n(1≦n≦3×104) 代表序列中的元素数量。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^5\right)$ 代表给定的序列。
输出格式
在一行上输出一个整数,代表序列中 "thair" 的个数。
测试样例
4
2 1 3 4
2
样例 1 解释
序列为 {2,1,3,4},满足条件的三个数共有 2 组:
∙取 a1=2、a3=3、a4=4,对应下标 1<3<4 且 2<3<4;
∙取 a2=1、a3=3、a4=4,对应下标 2<3<4 且 1<3<4。
因此答案为 2。
5
1 2 2 3 4
7
提示
对于 30% 的数据,1≦n≦100;
对于 60% 的数据,1≦n≦2×103;
对于 100% 的数据,1≦n≦3×104,1≦ai≦105。