题目描述

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

输入格式

输入的第一行是一个整数 $n$，表示勇士的数目。

接下来一行包括 $n$ 个整数，表示每个勇士的战斗值 $a_i$。

输出格式

输出为一行，包含一个整数。表示这队勇士的弱点数目。

4
10 8 3 1

4

样例分析

$(1,2,3)$、$(1,2,4)$、$(1,3,4)$ 和 $(2,3,4)$ 共 $4$ 个弱点。

数据范围与提示

对于 $30\%$的数据：$3 \le n \le 100$；

对于 $100\%$ 的数据，$3 \le n \le 10^6$，$1 \le a_i \le 10^6$，每个 $a_i$ 均不相同。