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