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()