Maxed Arrays

An array of integers X of length N is called Maxed with respect to a particular element K inside it if:

1. 3 <= N
2. If the index of the element K is i, then 1 < i < N
3. max(X[1], … , X[i]) ≠ max(X[2], … , X[i])
4. max(X[i], … , X[N]) ≠ max(X[i], … , X[N-1])

Given an array A of integers, for each element in A from index 1 to |A|, you need to find the sum of the length of all the subarrays of A that are Maxed with respect to each of these elements. Output is an array B where B[i] denotes the sum of the length of all the Maxed subarrays with respect to A[i].

1 <= |A| <= 10⁵

0 <= A[i] <= 10⁹

The first argument is an integer array A.

Return an integer array, the answer for each element in A.

Input 1:

A = [0, 2, 1]

Input 2:

A = [5, 3, 2, 5, 7]

Output 1:

[0, 0, 0]

Output 2:

[0, 9, 16, 0, 0]

For Input 1:

There is no subarray for the 0th element because it would always be the first element in each subarray.
For the 1st element, there is only the subarray [0, 2, 1] which satisfies the first 2 conditions. But it doesn’t satisfy the 2nd condition as max(0, 2) = max(2).
There is no subarray for 2nd element because it would always be the last element in each subarray.

For Input 2:

There is no subarray for the 0th element because it would always be the first element in each subarray.
The 2 subarrays that satisfy the conditions for the 1st element are [5, 3, 2, 5] and [5, 3, 2, 5, 7]. The sum of lengths is 4 + 5 = 9.
A total of 4 subarrays satisfy the conditions for the 2nd element - [5, 3, 2, 5], [5, 3, 2, 5, 7], [3, 2, 5, 7] and [3, 2, 5]. Sum = 3 + 4 + 4 + 5 = 16.
No subarray satisfies the conditions for the 3rd and 4th elements.