#P1637. 三元上升子序列

三元上升子序列

题目描述

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

在含有 nn 个整数的序列 a1,a2,,ana_1,a_2,\ldots,a_n 中,三个数被称作thair当且仅当 i<j<ki<j<kai<aj<aka_i<a_j<a_k

求一个序列中 thair 的个数。

输入格式

开始一行一个正整数 nn,

以后一行 nn 个整数 a1,a2,,ana_1,a_2,\ldots,a_n

输出格式

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

4
2 1 3 4
2
5
1 2 2 3 4
7

提示

样例2 解释

77thair 分别是:

  • 1 2 3
  • 1 2 4
  • 1 2 3
  • 1 2 4
  • 1 3 4
  • 2 3 4
  • 2 3 4

数据规模与约定

  • 对于 30%30\% 的数据 保证 n100n\le100
  • 对于 60%60\% 的数据 保证 n2000n\le2000
  • 对于 100%100\% 的数据 保证 1n3×1041 \leq n\le3\times10^40ai1050\le a_i\leq 10^5