题目描述

一队勇士正在向你进攻，每名勇士都有一个战斗值$\red{ai}$。但是这队勇士却有一个致命弱点，如果存在$\red{i<j<k}$使得$\red{ai>aj>ak，}$则会影响他们整体的战斗力。我们将这样的一组$\red{(i,j,k)}$称 为这队勇士的一个弱点。请求出这队勇士的弱点数目。

输入格式

输入文件：$\red{weakness.in}$ 输入的第一行是一个整数$\red{n，}$表示勇士的数目。 接下来一行包括$\red{n}$个整数，表示每个勇士的战斗值$\red{ai}$。

输出格式

输入文件：$\red{weakness.out}$ 输出为一行，包含一个整数。表示这队勇士的弱点数目。

样例

输入样例

4
10 8 3 1

输出样例

4

提示

对于$\red{30\%}$的数据，$\red{3<=n<=100}$

对于$\red{100\%}$的数据，$\red{3<=n<=1000000}$

对于$\red{100\%}$的数据，$\red{1<=ai<=1000000，}$每个$\red{ai}$均不相同