Question
Count Increasing Pairs in an Array
You are given an integer array A of length N.
Your task is to count the number of pairs (i, j) such that:
0 ≤ i < j < NA[i] < A[j]
Each valid pair should be counted exactly once.
Input
- The first line contains an integer
N, the size of the array. - The second line contains
Nspace-separated integers.
Output
Print a single integer — the count of all pairs
(i, j) such that A[i] < A[j] and i < j.Example
Example 1:
Input
4
1 3 2 4
Output
5
Explanation:
Valid pairs are:
(0,1) → 1 < 3
(0,2) → 1 < 2
(0,3) → 1 < 4
(1,3) → 3 < 4
(2,3) → 2 < 4
Example 2:
Input
5
1 2 3 4 5
Output
10
Explanation:
All possible pairs satisfy the condition
Number of pairs = C(5, 2) = 10.
Input
4
1 3 2 4
Output
5
Explanation:
Valid pairs are:
(0,1) → 1 < 3
(0,2) → 1 < 2
(0,3) → 1 < 4
(1,3) → 3 < 4
(2,3) → 2 < 4
Example 2:
Input
5
1 2 3 4 5
Output
10
Explanation:
All possible pairs satisfy the condition
A[i] < A[j].
Number of pairs = C(5, 2) = 10.