#949. 三元上升子序列

三元上升子序列

题目描述

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

在含有 nn 个整数的序列 a1,a2,…,ana_1,a_2,\ldots,a_n 中,三个数被称作thair当且仅当 $i

输入格式

开始一行一个正整数 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

题目来源:洛谷 P1637