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 Hi, 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 Hi > Hj > Hk.

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 ≤ Hi ≤ 109.

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

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

Subtask 3 (46%): 1 ≤ N ≤ 106.

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}.


Submitting .cpp to 'singlefile'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 256MB
No. of ACs: 56
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 0
2 19
3 35
4 46