转载请注明出处：http://www.cnblogs.com/ligun123/archive/2013/04/01/2993966.html
There is an integer array d which does not contain more than two elements of the same value. How many distinct ascending triples (d[i] < d[j] < d[k], i < j < k) are present?
Input format
The first line contains an integer N denoting the number of elements in the array. This is followed by a single line containing N integers separated by a single space with no leading/trailing spaces
Output format:
A single integer that denotes the number of distinct ascending triples present in the array
Constraints:
N <= 10^5
Every element of the array is present at most twice
Every element of the array is a 32-bit non-negative integer
Sample input:
6
1 1 2 2 3 4
Sample output:
4
Explanation:
The distinct triplets are
(1,2,3)
(1,2,4)
(1,3,4)
(2,3,4)
The elements of the array might not be sorted. Make no assumptions of the same.
解题思路：设Bi为数组d中从第i个元素开始比第i个元素大的元素的个数，那么关于第i个元素可以组成的升序序列个数Ri = Bk + B(k+1) + ...+ B(k), i <=k<=N,且 d[k] > d[i]