Description

Erwin has recently become very interested in something called thair...

In a sequence with $n$ integers $a_1,a_2,\ldots,a_n$, three numbers are called thair if and only if $i<j<k$ and $a_i<a_j<a_k$.

Find the number of thair in the sequence.

Input Format

The first line contains a positive integer $n$.

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

Output Format

Print one integer in a single line indicating the number of thair.

4
2 1 3 4

2

5
1 2 2 3 4

7

Hint

Sample 2 Explanation

The $7$ thair are:

• 1 2 3.
• 1 2 4.
• 1 2 3.
• 1 2 4.
• 1 3 4.
• 2 3 4.
• 2 3 4.

Constraints

• For $30\%$ of the testdata, it is guaranteed that $n\le100$.
• For $60\%$ of the testdata, it is guaranteed that $n\le2000$.
• For $100\%$ of the testdata, it is guaranteed that $1 \leq n\le3\times10^4$ and $1\le a_i\leq 10^5$.

Translated by ChatGPT 5