Meow Sequence

Problem Description

Given a sequence of $n$ integers $a_1, a_2, \dots, a_n$, a triple $(i, j, k)$ is called cute if and only if $i < j < k$ and $a_i < a_j < a_k$.

Count how many cute triples $(i, j, k)$ there are.

Input Format

The first line contains an integer $n$: the number of elements in the sequence.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$.

Output Format

Output one integer: the number of cute triples.

Sample Input

5
1 2 2 3 4

Sample Output

7

Sample Explanation

The valid triples are $(1, 2, 3)$, $(1, 2, 4)$, $(1, 2, 3)$, $(1, 2, 4)$, $(1, 3, 4)$, $(2, 3, 4)$, $(2, 3, 4)$, $7$ in total.

Constraints

$1 \le n \le 3 \times 10^4$, $0 \le a_i < 2^{63}$.