singlefile

Problem Description

After successfully assigning his N participants to groups and completing the activity, Damian now has them back in single file.

Of course, each student has his/her own height H_i, making the line lack uniformity and thus look rather messy.

Damian wants to quantify just how messy the line is. Thus, he wants to know how many triplets of students i, j, k exist, where i < j < k in the line and H_i > H_j > H_k.

Input

The first line contains one integer, N, the number of participants.

The second line contains N space-separated integers, with the ith integer representing the height of the ith participant.

Output

The output should contain one line containing one integer, the number of such triplets.

Limits

For all subtasks, 1 ≤ H_i ≤ 10⁹.

Subtask 1 (19%): 1 ≤ N ≤ 500.

Subtask 2 (35%): 1 ≤ N ≤ 10 000.

Subtask 3 (46%): 1 ≤ N ≤ 10⁶.

Subtask 4 (0%): Sample Testcases.

Sample Testcase 1

Input

5
9 3 7 4 1

Output

5

Sample Testcase 1 Explanation

The triplets are {9, 3, 1}, {9, 7, 4}, {9, 7, 1}, {9, 4, 1} and {7, 4, 1}.