题目描述

可可有很多的兄弟，今天他们都来找可可玩了，可可想统计一下他的兄弟中可以组成多少铁三角。可可的兄弟们会按照认识可可的先后顺序排队，三个人被称作铁三角当且仅当 $i<j<k$ 且 $a_i<a_j<a_k$。

PS：其中$a_i$ 表示第$i$个认识可可的兄弟的身高。可可的每一个兄弟身高都不同。

求铁三角个数。

输入格式

开始一行一个正整数 $n$,表示可可兄弟的个数。

以后一行 $n$ 个整数 以认识可可的先后顺序输入$a_1,a_2,\ldots,a_n$，

输出格式

一行一个整数表示铁三角的个数。

样例

4
2 3 1 4

1

4
2 1 3 4

2

数据范围

• 对于 $30\%$ 的数据 保证 $n\le100$；
• 对于 $60\%$ 的数据 保证 $n\le2000$；
• 对于 $100\%$ 的数据 保证 $1 \leq n\le3\times10^4$，$1\le a_i\leq 10^9$。