Question
Count Increasing Triplets
You are given a list of integers arr of length n.
Your task is to count the number of triplets of indices (i, j, k) such that:
-
i < j < k -
arr[i] < arr[j] < arr[k]
In other words, you must find how many strictly increasing triplets exist in the list.
Input
- First line contains an integer n — the number of elements in the list.
- Second line contains n space-separated integers.
Output
Print a single integer — the number of valid increasing triplets
Example
Example 1
Input:
5
1 2 3 4 5
Output:
10
Explanation:
All combinations of (i, j, k) where i < j < k form increasing triplets.
Example 2
Input:
5
3 1 2 4 0
Output:
1
Explanation:
Only one triplet satisfies the condition:
(1, 2, 4) → 1 < 2 < 4
Input:
5
1 2 3 4 5
Output:
10
Explanation:
All combinations of (i, j, k) where i < j < k form increasing triplets.
Example 2
Input:
5
3 1 2 4 0
Output:
1
Explanation:
Only one triplet satisfies the condition:
(1, 2, 4) → 1 < 2 < 4