from sys import stdin, stdout

input = stdin.readline


# O(N*Q)
# N, Q = 0, 0
def main(Q, N, Prices):
    # N,Q = list(map(int, input().split()))
    # N,Q = [int(x) for x in input().split()]
    # N = NQ[0]
    # Q = NQ[1]
    # Prices = list(map(int, stdin.readline().split()))
    # balance = [0]*Q

    for i in range(Q):
        isHolding = False
        curBalance = 0
        lo, hi = list(map(int, stdin.readline().split()))
        for f in Prices:
            if not isHolding:
                if lo >= f:
                    curBalance -= f
                    isHolding = True
            elif hi <= f:
                curBalance += f
                isHolding = False
        # balance.append(curBalance)
        # balance[i]=curBalance

        # for i in balance:
        stdout.write(str(curBalance) + '\n')


# main()

# 5 10 10 10 5 5 5 5
# Q:
# 6 9
# 7 8
# 6 8
def ketszam():
    N, Q = list(map(int, input().split()))
    Prices = list(map(int, stdin.readline().split()))
    first = Prices[0]
    second = 0

    if Q <= 50:
        main(Q, N, Prices)
        return

    for i in Prices:  # range(1,len(Prices)))
        if i != first:
            second = i

    if second < first:
        second, first = first, second

    fourth = False
    fourthBalance = 0
    for i in range(Q):
        lo, hi = list(map(int, stdin.readline().split()))
        if lo < first:
            stdout.write('0\n')
        elif hi > second:
            if lo >= second and Prices[0] == second:
                stdout.write(str(-second) + '\n')
            else:
                stdout.write(str(-first) + '\n')
        else:
            if fourth == False:
                fourth = True
                isHolding = False
                curBalance = 0
                for f in Prices:
                    if not isHolding:
                        if lo >= f:
                            curBalance -= f
                            isHolding = True
                    elif hi <= f:
                        curBalance += f
                        isHolding = False

                stdout.write(str(curBalance) + '\n')
                fourthBalance = curBalance
            else:
                stdout.write(str(fourthBalance) + '\n')


#ketszam()

def solv():
    N, Q = list(map(int, input().split()))
    Prices = list(map(int, stdin.readline().split()))
    Valasz = [[0] * 501 for i in range(501)]

    # haszon
    for lo in range(1, 500):
        delta = [0] * 501
        utolsoElad = 501
        for ar in Prices:
            if ar <= lo:
                utolsoElad = lo
            elif utolsoElad < ar:
                delta[utolsoElad] += ar
                delta[ar] -= ar
                utolsoElad = ar
        # if lo==41:
        #    print(Prices)
        #    print(delta)
        #    print(delta[41],delta[80],delta[100],delta[120],delta[125])

        szumma = delta[lo]
        for eladas in range(lo + 1, 501):
            Valasz[lo][eladas] = szumma
            szumma += delta[eladas]

    # vetel
    for hi in range(500, 1, -1):
        delta = [0] * 501
        utolsoVesz = hi
        for ar in Prices:
            if ar >= hi:
                utolsoVesz = hi
            elif utolsoVesz > ar:
                delta[utolsoVesz] += ar
                delta[ar] -= ar
                utolsoVesz = ar
        # if hi==41:
        #    print(Prices)
        #    print(delta)
        #    print(delta[30],delta[40],delta[41],delta[120],delta[125])

        szumma = delta[hi]
        for eladas in range(hi - 1, 0, -1):
            Valasz[eladas][hi] -= szumma
            szumma += delta[eladas]

    for _ in range(Q):
        lo, hi = list(map(int, stdin.readline().split()))
        stdout.write(str(Valasz[lo][hi]) + '\n')


solv()