```go
package main

import (
	"io"
	"os"
	"strconv"
)

func nextInt(data []byte, idx *int) int {
	i := *idx
	n := len(data)
	for i < n && (data[i] < '0' || data[i] > '9') {
		i++
	}
	val := 0
	for i < n && data[i] >= '0' && data[i] <= '9' {
		val = val*10 + int(data[i]-'0')
		i++
	}
	*idx = i
	return val
}

func countSort(keys []int32, m, maxKey int, cnt []int, ord []int32) {
	for i := 0; i <= maxKey; i++ {
		cnt[i] = 0
	}
	for i := 1; i <= m; i++ {
		cnt[int(keys[i])]++
	}
	for i := 1; i <= maxKey; i++ {
		cnt[i] += cnt[i-1]
	}
	for i := m; i >= 1; i-- {
		k := int(keys[i])
		ord[cnt[k]] = int32(i)
		cnt[k]--
	}
}

func add(bitCnt []int32, bitSum []int64, n, idx int, dsum int64) {
	for idx <= n {
		bitCnt[idx]++
		bitSum[idx] += dsum
		idx += idx & -idx
	}
}

func prefix(bitCnt []int32, bitSum []int64, idx int) (int64, int64) {
	var c int64
	var s int64
	for idx > 0 {
		c += int64(bitCnt[idx])
		s += bitSum[idx]
		idx -= idx & -idx
	}
	return c, s
}

func main() {
	data, _ := io.ReadAll(os.Stdin)
	ptr := 0

	n := nextInt(data, &ptr)
	q := nextInt(data, &ptr)

	left := make([]int32, n+1)
	right := make([]int32, n+1)

	stackIdx := make([]int32, n+1)
	stackVal := make([]int32, n+1)
	top := 0

	for i := 1; i <= n; i++ {
		x := int32(nextInt(data, &ptr))
		var last int32
		for top > 0 && stackVal[top-1] < x {
			top--
			last = stackIdx[top]
		}
		if top > 0 {
			right[int(stackIdx[top-1])] = int32(i)
		}
		if last != 0 {
			left[i] = last
		}
		stackIdx[top] = int32(i)
		stackVal[top] = x
		top++
	}

	root := stackIdx[0]

	l := make([]int32, q+1)
	r := make([]int32, q+1)
	for i := 1; i <= q; i++ {
		l[i] = int32(nextInt(data, &ptr))
	}
	for i := 1; i <= q; i++ {
		r[i] = int32(nextInt(data, &ptr))
	}

	L := make([]int32, n+1)
	R := make([]int32, n+1)

	order := stackVal
	top = 0
	stackIdx[top] = root
	top++
	k := 0
	for top > 0 {
		top--
		v := stackIdx[top]
		order[k] = v
		k++
		vi := int(v)
		if left[vi] != 0 {
			stackIdx[top] = left[vi]
			top++
		}
		if right[vi] != 0 {
			stackIdx[top] = right[vi]
			top++
		}
	}
	for i := k - 1; i >= 0; i-- {
		v := order[i]
		vi := int(v)
		lc := left[vi]
		rc := right[vi]
		if lc != 0 {
			L[vi] = L[int(lc)]
		} else {
			L[vi] = v
		}
		if rc != 0 {
			R[vi] = R[int(rc)]
		} else {
			R[vi] = v
		}
	}

	ordN := make([]int32, n+1)
	ordQ := make([]int32, q+1)
	cnt := make([]int, n+1)
	bitCnt := make([]int32, n+2)
	bitSum := make([]int64, n+2)
	ans := make([]int64, q+1)

	countSort(L, n, n, cnt, ordN)
	countSort(l, q, n, cnt, ordQ)

	pn := n
	for i := q; i >= 1; i-- {
		id := int(ordQ[i])
		li := int(l[id])
		ri := int(r[id])
		for pn > 0 {
			node := int(ordN[pn])
			if int(L[node]) <= li {
				break
			}
			add(bitCnt, bitSum, n, node, int64(L[node]))
			pn--
		}
		c1, s1 := prefix(bitCnt, bitSum, ri)
		c0, s0 := prefix(bitCnt, bitSum, li-1)
		c := c1 - c0
		s := s1 - s0
		length := int64(ri - li + 1)
		ans[id] = length*length - (s - int64(li)*c)
	}

	for i := 1; i <= n; i++ {
		bitCnt[i] = 0
		bitSum[i] = 0
	}

	countSort(R, n, n, cnt, ordN)
	countSort(r, q, n, cnt, ordQ)

	pn = 1
	for i := 1; i <= q; i++ {
		id := int(ordQ[i])
		li := int(l[id])
		ri := int(r[id])
		for pn <= n {
			node := int(ordN[pn])
			if int(R[node]) >= ri {
				break
			}
			add(bitCnt, bitSum, n, node, int64(R[node]))
			pn++
		}
		c1, s1 := prefix(bitCnt, bitSum, ri)
		c0, s0 := prefix(bitCnt, bitSum, li-1)
		c := c1 - c0
		s := s1 - s0
		ans[id] -= int64(ri)*c - s
	}

	out := make([]byte, 0, q*14+1)
	for i := 1; i <= q; i++ {
		out = strconv.AppendInt(out, ans[i], 10)
		if i < q {
			out = append(out, ' ')
		}
	}
	out = append(out, '\n')
	os.Stdout.Write(out)
}
```