Count subarrays for every array element in which they are the minimum | Function to find the boundary of every element within which it is minimum ; Perform Binary Search ; Find mid m ; Update l ; Update r ; Inserting the index ; Function to required count subarrays ; Stores the indices of element ; Initialize the output array ; Left boundary , till the element is smallest ; Right boundary , till the element is smallest ; Calculate the number of subarrays based on its boundary ; Adding cnt to the ans ; Driver Code ; Given array arr [ ] ; Function Call
def binaryInsert ( boundary , i ) : NEW_LINE INDENT l = 0 NEW_LINE r = len ( boundary ) - 1 NEW_LINE while l <= r : NEW_LINE INDENT m = ( l + r ) // 2 NEW_LINE if boundary [ m ] < i : NEW_LINE INDENT l = m + 1 NEW_LINE DEDENT else : NEW_LINE INDENT r = m - 1 NEW_LINE DEDENT DEDENT boundary . insert ( l , i ) NEW_LINE return l NEW_LINE DEDENT def countingSubarray ( arr , n ) : NEW_LINE INDENT index = { } NEW_LINE for i in range ( n ) : NEW_LINE INDENT index [ arr [ i ] ] = i NEW_LINE DEDENT boundary = [ - 1 , n ] NEW_LINE arr . sort ( ) NEW_LINE ans = [ 0 for i in range ( n ) ] NEW_LINE for num in arr : NEW_LINE INDENT i = binaryInsert ( boundary , index [ num ] ) NEW_LINE l = boundary [ i ] - boundary [ i - 1 ] - 1 NEW_LINE r = boundary [ i + 1 ] - boundary [ i ] - 1 NEW_LINE cnt = l + r + l * r + 1 NEW_LINE ans [ index [ num ] ] += cnt NEW_LINE DEDENT return ans NEW_LINE DEDENT N = 5 NEW_LINE arr = [ 3 , 2 , 4 , 1 , 5 ] NEW_LINE print ( countingSubarray ( arr , N ) ) NEW_LINE