Counting Thair Subsequences

Erwin is fascinated by a concept called thair. In a sequence of n integers, thair is defined as a triple of numbers a_i, a_j, a_k such that i < j < k and a_i < a_j < a_k. In other words, three numbers form a thair if and only if:

$i<j<k$ and $a_i<a_j<a_k$

Your task is to count the number of thair triples in the given sequence.

inputFormat

The input consists of two lines. The first line contains an integer n ($1 \leq n \leq 10^5$ depending on constraints). The second line contains n space-separated integers representing the sequence: a₁, a₂, ..., a_n.

outputFormat

Output a single integer, which is the number of thair triples in the given sequence.

sample

3
1 2 3

1