Problems
Yura and attractive array
Yura and attractive array
The monkey gave Yura an array a with n integers. Yura immediately wanted to determine the attractiveness of this array. He believes that the attractiveness of the array is the number of triples of indices i, j, k, such that 1 ≤ i < j < k ≤ n and ai
< aj
< ak
. But Yura still does not know how to program, so asked for your help.
Help Yura to find the attractiveness of the array.
Input
First line contains one integer n (1 ≤ n ≤ 105
) - the size of array. Second line contains n nonnegative integers - the array elements. All values do not exceed 106
.
Output
Print one number - the attractiveness of array.
Input example #1
4 1 3 8 10
Output example #1
4
Input example #2
3 1 3 2
Output example #2
0