Question
Count Dominant Triplets
You are given an integer array arr of length n.
A triplet (i, j, k) is called dominant if:
i < j < karr[j]is strictly greater than botharr[i]andarr[k]:arr[i] < arr[j] > arr[k]
Your task is to count how many dominant triplets exist in the array.
Input
First and only line contains n space-separated integers.
Output
Print the number of dominant triplets
Example
Example 1
Input:
1 3 2 4 1
Output:
6
Explanation:
Valid dominant triplets:
(1, 3, 2) → 3 is greater than 1 and 2
(1, 3, 1) → 3 is greater than 1 and 1
(1, 2, 1) → 2 is greater than 1 and 1
(1, 4, 1) → 4 is greater than 1 and 1
(3, 4, 1) → 4 is greater than 3 and 1
(2, 4, 1) → 4 is greater than 2 and 1
Example 2
Input:
2 2 2 2
Output:
0
Explanation:
No element is strictly greater than both its neighbors.
Input:
1 3 2 4 1
Output:
6
Explanation:
Valid dominant triplets:
(1, 3, 2) → 3 is greater than 1 and 2
(1, 3, 1) → 3 is greater than 1 and 1
(1, 2, 1) → 2 is greater than 1 and 1
(1, 4, 1) → 4 is greater than 1 and 1
(3, 4, 1) → 4 is greater than 3 and 1
(2, 4, 1) → 4 is greater than 2 and 1
Example 2
Input:
2 2 2 2
Output:
0
Explanation:
No element is strictly greater than both its neighbors.