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.