LG#P1637. 三元上升子序列

三元上升子序列

P1637 三元上升子序列

题目描述

\hspace{15pt}Erwin 最近对一种叫做 "thair"\texttt{"thair"} 的东西非常感兴趣。

\hspace{15pt}在含有 nn 个整数的序列 {a1,a2,…,an}\{a_1, a_2, \dots, a_n\} 中,若三个下标 i,j,ki, j, k 满足 i<j<ki<j<k 且 ai<aj<aka_i<a_j<a_k,则称这三个数构成一个 "thair"\texttt{"thair"}。

\hspace{15pt}给定一个序列,请你求出其中 "thair"\texttt{"thair"} 的个数。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦3×104)n \left(1 \leqq n \leqq 3 \times 10^4\right) 代表序列中的元素数量。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^5\right)$ 代表给定的序列。

输出格式

\hspace{15pt}在一行上输出一个整数,代表序列中 "thair"\texttt{"thair"} 的个数。

测试样例

4
2 1 3 4
2

样例 1 解释

\hspace{15pt}序列为 {2,1,3,4}\{2, 1, 3, 4\},满足条件的三个数共有 22 组:

∙ \hspace{23pt}\bullet\,取 a1=2a_1=2、a3=3a_3=3、a4=4a_4=4,对应下标 1<3<41<3<4 且 2<3<42<3<4;

∙ \hspace{23pt}\bullet\,取 a2=1a_2=1、a3=3a_3=3、a4=4a_4=4,对应下标 2<3<42<3<4 且 1<3<41<3<4。

\hspace{15pt}因此答案为 22。

5
1 2 2 3 4
7

提示

\hspace{15pt}对于 30%30\% 的数据,1≦n≦1001 \leqq n \leqq 100;

\hspace{15pt}对于 60%60\% 的数据,1≦n≦2×1031 \leqq n \leqq 2 \times 10^3;

\hspace{15pt}对于 100%100\% 的数据,1≦n≦3×1041 \leqq n \leqq 3 \times 10^4,1≦ai≦1051 \leqq a_i \leqq 10^5。