package main

import (
	"bufio"
	"os"
	"strconv"
)

type FastScanner struct {
	r *bufio.Reader
}

func NewFastScanner() *FastScanner {
	return &FastScanner{r: bufio.NewReaderSize(os.Stdin, 1<<20)}
}

func (fs *FastScanner) nextInt() int {
	sign := 1
	v := 0
	c, err := fs.r.ReadByte()
	for (c < '0' || c > '9') && c != '-' {
		c, err = fs.r.ReadByte()
		if err != nil {
			return 0
		}
	}
	if c == '-' {
		sign = -1
		c, _ = fs.r.ReadByte()
	}
	for c >= '0' && c <= '9' {
		v = v*10 + int(c-'0')
		c2, err := fs.r.ReadByte()
		if err != nil {
			break
		}
		c = c2
	}
	return v * sign
}

type Fenwick struct {
	n     int
	b1, b2 []int64
}

func NewFenwick(n int) *Fenwick {
	return &Fenwick{
		n:  n,
		b1: make([]int64, n+2),
		b2: make([]int64, n+2),
	}
}

func (f *Fenwick) add(bit []int64, idx int, delta int64) {
	for idx <= f.n {
		bit[idx] += delta
		idx += idx & -idx
	}
}

func (f *Fenwick) sum(bit []int64, idx int) int64 {
	var res int64
	for idx > 0 {
		res += bit[idx]
		idx -= idx & -idx
	}
	return res
}

func (f *Fenwick) rangeAdd(l, r int, delta int64) {
	if delta == 0 || l > r {
		return
	}
	f.add(f.b1, l, delta)
	f.add(f.b1, r+1, -delta)
	f.add(f.b2, l, delta*int64(l-1))
	f.add(f.b2, r+1, -delta*int64(r))
}

func (f *Fenwick) prefixSum(idx int) int64 {
	if idx <= 0 {
		return 0
	}
	s1 := f.sum(f.b1, idx)
	s2 := f.sum(f.b2, idx)
	return s1*int64(idx) - s2
}

type Pair struct {
	l, idx int
}

type Block struct {
	L, R int
	val  int64
}

func main() {
	in := NewFastScanner()
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	n := in.nextInt()
	c := make([]int64, n+1)
	for i := 1; i <= n; i++ {
		c[i] = int64(in.nextInt())
	}
	q := in.nextInt()
	queriesByR := make([][]Pair, n+1)
	for i := 0; i < q; i++ {
		l := in.nextInt()
		r := in.nextInt()
		queriesByR[r] = append(queriesByR[r], Pair{l: l, idx: i})
	}

	ans := make([]int64, q)
	fw := NewFenwick(n)
	stack := make([]Block, 0)

	for t := 1; t <= n; t++ {
		x := c[t]
		start := t
		for len(stack) > 0 && stack[len(stack)-1].val <= x {
			b := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			delta := x - b.val
			if delta != 0 {
				fw.rangeAdd(b.L, b.R, delta)
			}
			start = b.L
		}
		stack = append(stack, Block{L: start, R: t, val: x})
		fw.rangeAdd(t, t, x)

		prefR := fw.prefixSum(t)
		for _, qu := range queriesByR[t] {
			l := qu.l
			ans[qu.idx] = prefR - fw.prefixSum(l-1)
		}
	}

	for i := 0; i < q; i++ {
		out.WriteString(strconv.FormatInt(ans[i], 10))
		out.WriteByte('\n')
	}
}