题目描述

给定一个含有 $n$ 个整数的序列 $a_1, a_2, \dots a_n$，三个数 $i, j, k$ 是可爱的当且仅当 $i < j < k$ 且 $a_i < a_j < a_k$。

请你求出有多少组 $i, j, k$ 是可爱的。

输入格式

第 $1$ 行一个整数 $n$ 表示序列元素个数。

第 $2$ 行 $n$ 个整数分别表示 $a_1, a_2, \dots a_n$。

输出格式

一行一个整数，表示所求数量。

样例输入

5
1 2 2 3 4

样例输出

7

样例说明

满足条件的有：$(1, 2, 3)$，$(1, 2, 4)$，$(1, 2, 3)$，$(1, 2, 4)$，$(1, 3, 4)$，$(2, 3, 4)$，$(2, 3, 4)$，共 $7$ 个。

数据范围

对于全部数据，有 $1 \le n \le 3 \times 10^4$，$0 \le a_i < 2^{63}$。

双倍经验