Count Increasing Pairs

Problem Statement

Count Increasing Pairs Given an array arr of n integers, count its strictly increasing subsequences of length 2. A subsequence is what is left after deleting zero or more elements without changing the order of the elements that remain, so a subsequence of length 2 is a pair of positions i and j with i < j , and it is strictly increasing when arr[i] < arr[j] . Report how many such pairs of positions exist. Input Format Line 1 contains a single integer n , the length of the array. Line 2 contains n space separated integers, the elements of arr . Output Format Print a single integer: the number of pairs (i, j) with i < j and arr[i] < arr[j] . Print 0 when there is none. Constraints 1 <= n <= 5000 -1000000000 <= arr[i] <= 1000000000 *(inferred -- the element bound in the source screenshot is cut off at the edge of the image; this symmetric range is used because the published examples contain negative elements.)* The answer is at most 12497500, so a 32-bit signed int