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 a[i] < a[j] < a[k]. 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 ≤ 10^5) - the size of array. Second line contains n nonnegative integers - the array elements. All values do not exceed 10^6.

Output

Print one number - the attractiveness of array.

Examples