Question:
You are given an array arr of N integers. For each index i, you are required to determine the number of contiguous subarrays that fulfill the following conditions:

1. The value at index i must be the maximum element in the contiguous subarrays, and
2. These contiguous subarrays must either start from or end on index i.

Example:
arr = [3, 4, 1, 6, 2]
output = [1, 3, 1, 5, 1]
Explanation:
For index 0 - [3] is the only contiguous subarray that starts (or ends) with 3, and the maximum value in this subarray is 3.
For index 1 - [4], [3, 4], [4, 1]
For index 2 - [1]
For index 3 - [6], [6, 2], [1, 6], [4, 1, 6], [3, 4, 1, 6]
For index 4 - [2]
So, the answer for the above input is [1, 3, 1, 5, 1]

Signature
int[] countSubarrays(int[] arr)
Input
Array arr is a non-empty list of unique integers that range between 1 to 1,000,000,000
Size N is between 1 and 1,000,000
Output
An array where each index i contains an integer denoting the maximum number of contiguous subarrays of arr[i]
-----------------------------------------------------------------
Brute Force approach: O(n^2)
Monotonic stack : O(2n) time complexity and O(4n) space complexity

Solution: We only need the count of possible subarrays for every element where element is the largest number. So our problem reduces to find the number of elements which are less than the current element being processed.

def count_subarrays(arr):
  arr_stack, index_stack, count_stack = [], [], []
  res = [0 for _ in range(len(arr))]
  index, prev_max_count = 0, 0
  
  # using monotonic stack concept 
  # iterate until the length of arr or stack is empty
  while (index < len(arr)) or len(arr_stack) > 0:
    # push into stack if stack is empty or curr_element is < top of stack
    # push index -> index_stack (we need index later to update res list) 
    # push prev_max_count value into count_stack (which gives elements less than the curr element)
    # reset prev_max_count to zero (because now we need to calculate how many more elements are less than curr element)
    
    if len(arr_stack) == 0 or (index < len(arr) and arr[index] < arr_stack[-1]):
      arr_stack.append(arr[index])
      index_stack.append(index)
      count_stack.append(prev_max_count)
      prev_max_count = 0
      index += 1
    
    else:
      if arr_stack:
        arr_stack.pop()
        prev_max_count += 1  
        curr_index      = index_stack.pop()
        prev_max_count  += count_stack.pop()
        res[curr_index]    +=  prev_max_count
  return res