245246247248249250251252253254255256257258259260261262263264265266
package main

import (
	"fmt"
)

/* Function to find the indices of
next smaller elements */
func findNSE(arr []int) []int {

	// Size of array
	n := len(arr)

	// To store the answer
	ans := make([]int, n)

	// Stack
	st := []int{}

	// Start traversing from the back
	for i := n - 1; i >= 0; i-- {

		// Get the current element
		currEle := arr[i]

		/* Pop the elements in the stack until
		the stack is not empty and the top
		element is not the smaller element */
		for len(st) > 0 && arr[st[len(st)-1]] >= currEle {
			st = st[:len(st)-1]
		}

		// Update the answer
		if len(st) > 0 {
			ans[i] = st[len(st)-1]
		} else {
			ans[i] = n
		}

		/* Push the index of current
		element in the stack */
		st = append(st, i)
	}

	// Return the answer
	return ans
}

/* Function to find the indices of
next greater elements */
func findNGE(arr []int) []int {

	// Size of array
	n := len(arr)

	// To store the answer
	ans := make([]int, n)

	// Stack
	st := []int{}

	// Start traversing from the back
	for i := n - 1; i >= 0; i-- {

		// Get the current element
		currEle := arr[i]

		/* Pop the elements in the stack until
		the stack is not empty and the top
		element is not the greater element */
		for len(st) > 0 && arr[st[len(st)-1]] <= currEle {
			st = st[:len(st)-1]
		}

		// Update the answer
		if len(st) > 0 {
			ans[i] = st[len(st)-1]
		} else {
			ans[i] = n
		}

		/* Push the index of current
		element in the stack */
		st = append(st, i)
	}

	// Return the answer
	return ans
}

/* Function to find the indices of
previous smaller or equal elements */
func findPSEE(arr []int) []int {

	// Size of array
	n := len(arr)

	// To store the answer
	ans := make([]int, n)

	// Stack
	st := []int{}

	// Traverse on the array
	for i := 0; i < n; i++ {

		// Get the current element
		currEle := arr[i]

		/* Pop the elements in the stack until
		the stack is not empty and the top
		elements are greater than the current element */
		for len(st) > 0 && arr[st[len(st)-1]] > currEle {
			st = st[:len(st)-1]
		}

		// Update the answer
		if len(st) > 0 {
			ans[i] = st[len(st)-1]
		} else {
			ans[i] = -1
		}

		/* Push the index of current
		element in the stack */
		st = append(st, i)
	}

	// Return the answer
	return ans
}

/* Function to find the indices of
previous greater or equal elements */
func findPGEE(arr []int) []int {

	// Size of array
	n := len(arr)

	// To store the answer
	ans := make([]int, n)

	// Stack
	st := []int{}

	// Traverse on the array
	for i := 0; i < n; i++ {

		// Get the current element
		currEle := arr[i]

		/* Pop the elements in the stack until
		the stack is not empty and the top
		elements are smaller than the current element */
		for len(st) > 0 && arr[st[len(st)-1]] < currEle {
			st = st[:len(st)-1]
		}

		// Update the answer
		if len(st) > 0 {
			ans[i] = st[len(st)-1]
		} else {
			ans[i] = -1
		}

		/* Push the index of current
		element in the stack */
		st = append(st, i)
	}

	// Return the answer
	return ans
}

/* Function to find the sum of the
minimum value in each subarray */
func sumSubarrayMins(arr []int) int64 {

	nse := findNSE(arr)
	psee := findPSEE(arr)

	// Size of array
	n := len(arr)

	// To store the sum
	var sum int64 = 0

	// Traverse on the array
	for i := 0; i < n; i++ {

		// Count of first type of subarrays
		left := i - psee[i]

		// Count of second type of subarrays
		right := nse[i] - i

		/* Count of subarrays where
		current element is minimum */
		freq := int64(left * right)

		// Contribution due to current element
		val := freq * int64(arr[i])

		// Updating the sum
		sum +=