You are beta testing the new secret Terraria update. This update will add quests to the game!

Simply, the world map can be represented as an array of length $n$, where the $i$-th column of the world has height $a_i$.

There are $m$ quests you have to test. The $j$-th of them is represented by two integers $s_j$ and $t_j$. In this quest, you have to go from the column $s_j$ to the column $t_j$. At the start of the quest, you are appearing at the column $s_j$.

In one move, you can go from the column $x$ to the column $x-1$ or to the column $x+1$. In this version, you have Spectre Boots, which allow you to fly. Since it is a beta version, they are bugged, so they only allow you to fly when you are going up and have infinite fly duration. When you are moving from the column with the height $p$ to the column with the height $q$, then you get some amount of fall damage. If the height $p$ is greater than the height $q$, you get $p - q$ fall damage, otherwise you fly up and get $0$ damage.

For each of the given quests, determine the minimum amount of fall damage you can get during this quest.


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($2 \le n \le 10^5; 1 \le m \le 10^5$) — the number of columns in the world and the number of quests you have to test, respectively.

The second line of the input contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the height of the $i$-th column of the world.

The next $m$ lines describe quests. The $j$-th of them contains two integers $s_j$ and $t_j$ ($1 \le s_j, t_j \le n; s_j \ne t_j$), which means you have to move from the column $s_j$ to the column $t_j$ during the $j$-th quest.

Note that $s_j$ can be greater than $t_j$.


-----Output-----

Print $m$ integers. The $j$-th of them should be the minimum amount of fall damage you can get during the $j$-th quest completion.


-----Examples-----

Input
7 6
10 8 9 6 8 12 7
1 2
1 7
4 6
7 1
3 5
4 2
Output
2
10
0
7
3
1


-----Note-----

None

Difficulty: EASY
Tags: Dynamic programming

Data structures

Implementation
Skill types: Dynamic programming

Data structures

Starter code:

Solutions:
import sys, math, itertools, functools, collections
input = sys.stdin.readline

def solve():
	(n, m) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	right = [0] * n
	left = [0] * n
	x = 0
	for i in range(1, n):
		if a[i - 1] > a[i]:
			x += a[i - 1] - a[i]
		right[i] = x
	x = 0
	for i in range(n - 2, -1, -1):
		if a[i + 1] > a[i]:
			x += a[i + 1] - a[i]
		left[i] = x
	for i in range(m):
		(p, q) = map(int, input().split(' '))
		if p < q:
			print(right[q - 1] - right[p - 1])
		else:
			print(left[q - 1] - left[p - 1])
solve()


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
board = list(map(int, input().split()))
board = [0] + board
cumul_forward = [0]
cumul_backward = [0]
for (a, b) in zip(board[:-1], board[1:]):
	if a - b < 0:
		cumul_backward.append(cumul_backward[-1] + b - a)
		cumul_forward.append(cumul_forward[-1])
	else:
		cumul_backward.append(cumul_backward[-1])
		cumul_forward.append(cumul_forward[-1] + a - b)
for _ in range(m):
	(st, ed) = map(int, input().split())
	if st < ed:
		print(cumul_forward[ed] - cumul_forward[st])
	else:
		print(cumul_backward[st] - cumul_backward[ed])


input = __import__('sys').stdin.readline

def solve():
	(n, m) = map(int, input().split())
	a = [0] + list(map(int, input().strip().split())) + [0]
	prefix = [0] * (n + 2)
	for i in range(2, n + 1):
		prefix[i] = prefix[i - 1] + max(0, a[i - 1] - a[i])
	suffix = [0] * (n + 2)
	for i in range(n - 1, 0, -1):
		suffix[i] = suffix[i + 1] + max(0, a[i + 1] - a[i])
	for _ in range(m):
		(s, t) = map(int, input().split())
		if s < t:
			print(prefix[t] - prefix[s])
		else:
			print(suffix[t] - suffix[s])
solve()


def main():
	(n, m) = map(int, input().split())
	nums = list(map(int, input().split()))
	(pos, neg) = ([0], [0])
	for i in range(n - 1):
		(a, b) = (nums[i], nums[i + 1])
		pos.append(damage(a, b) + pos[i])
		neg.append(damage(b, a) + neg[i])
	res = []
	for i in range(m):
		(s, t) = [int(i) - 1 for i in input().split()]
		if s < t:
			res.append(str(pos[t] - pos[s]))
		else:
			res.append(str(neg[s] - neg[t]))
	print('\n'.join(res))

def damage(a, b):
	return a - b if a > b else 0
main()


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * n
c = [0] * n
p = 0
for i in range(1, n):
	if a[i] < a[i - 1]:
		p += a[i - 1] - a[i]
		b[i] = p
	else:
		b[i] = p
p = 0
for i in range(n - 2, -1, -1):
	if a[i] < a[i + 1]:
		p += a[i + 1] - a[i]
		c[i] = p
	else:
		c[i] = p
for i in range(m):
	(s, t) = map(int, input().split())
	if s <= t:
		print(b[t - 1] - b[s - 1])
	else:
		print(c[t - 1] - c[s - 1])


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
li1 = [0]
li2 = [0]
for i in range(n - 1):
	li1.append(li1[i] + max(0, a[i] - a[i + 1]))
	li2.append(li2[i] + max(0, a[i + 1] - a[i]))
for i in range(m):
	(i, j) = map(int, input().split())
	if i < j:
		print(li1[j - 1] - li1[i - 1])
	else:
		print(li2[i - 1] - li2[j - 1])


import math
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
arr = [0] + arr + [0]
predmg = [0 if arr[i] < arr[i + 1] else arr[i] - arr[i + 1] for i in range(n)]
presumdmg = [0] * n
for i in range(1, n):
	presumdmg[i] = presumdmg[i - 1] + predmg[i]
postdmg = [0 if arr[i + 1] < arr[i] else arr[i] - arr[i + 1] for i in range(1, n + 1)]
postsumdmg = [0] * n
for i in range(n - 2, -1, -1):
	postsumdmg[i] = postsumdmg[i + 1] + postdmg[i]
for i in range(m):
	(s, t) = map(int, input().split())
	if s <= t:
		print(presumdmg[t - 1] - presumdmg[s - 1])
	else:
		print(postsumdmg[s - 1] - postsumdmg[t - 1])


from sys import stdin
rd = stdin.readline
(n, m) = map(int, rd().split())
a = list(map(int, rd().split()))
b = [0] + [max(0, a[i - 1] - a[i]) for i in range(1, n)]
c = [0] + [max(0, a[i] - a[i - 1]) for i in range(1, n)]
for i in range(1, n):
	b[i] += b[i - 1]
	c[i] += c[i - 1]
for _ in range(m):
	(s, t) = map(int, rd().split())
	if s <= t:
		print(b[t - 1] - b[s - 1])
	else:
		print(c[s - 1] - c[t - 1])


import sys
printf = sys.stdout.write

def intput():
	return int(sys.stdin.readline())

def get_int():
	return map(int, sys.stdin.readline().strip().split())

def get_lis():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_liss():
	return sys.stdin.readline().split()

def get_ints():
	return sys.stdin.readline().split()

def get_str():
	return sys.stdin.readline().strip()

def pop_zeros(items):
	while items[-1] == 0:
		items.pop()
from collections import defaultdict
import math
(n, m) = get_int()
lf = [0]
lr = [0]
cf = 0
cr = 0
l = get_lis()
for i in range(n - 1):
	if l[i + 1] < l[i]:
		cf += l[i] - l[i + 1]
		lf.append(cf)
	else:
		lf.append(cf)
	if l[n - i - 1] > l[n - i - 2]:
		cr += l[n - i - 1] - l[n - i - 2]
		lr.append(cr)
	else:
		lr.append(cr)
lr.reverse()
for i in range(m):
	(s, t) = get_int()
	if s < t:
		printf(str(lf[t - 1] - lf[s - 1]))
		printf('\n')
	else:
		printf(str(lr[t - 1] - lr[s - 1]))
		printf('\n')


x = input().split()
(n, m) = (int(x[0]), int(x[1]))
datan = [int(i) for i in input().split()]
datam = []
for i in range(m):
	x = input().split()
	(s, j) = (int(x[0]), int(x[1]))
	datam.append((s, j))

def solve(n, m, datan, datam):
	go_right = [0] * n
	sums = 0
	for i in range(1, n):
		if datan[i] < datan[i - 1]:
			sums += datan[i - 1] - datan[i]
		go_right[i] = sums
	go_left = [0] * n
	sums = 0
	for i in range(n - 2, -1, -1):
		if datan[i] < datan[i + 1]:
			sums += datan[i + 1] - datan[i]
		go_left[i] = sums
	for (s, j) in datam:
		if s > j:
			print(go_left[j - 1] - go_left[s - 1])
		else:
			print(go_right[j - 1] - go_right[s - 1])
solve(n, m, datan, datam)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = 1
for _ in range(1):
	(n, m) = mp()
	l = li()
	l1 = [0]
	l2 = [0]
	s = 0
	for i in range(n - 1):
		if l[i + 1] - l[i] < 0:
			s += abs(l[i + 1] - l[i])
		l1.append(s)
	s = 0
	for i in range(n - 1, 0, -1):
		if l[i] - l[i - 1] > 0:
			s += abs(l[i] - l[i - 1])
		l2.append(s)
	l2.reverse()
	for i in range(m):
		(a, b) = mp()
		if a <= b:
			pr(l1[b - 1] - l1[a - 1])
		else:
			pr(abs(l2[b - 1] - l2[a - 1]))


import io, os, sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
cols = list(map(int, input().split()))
cudlr = [0 for i in range(n)]
cudrl = [0 for i in range(n)]
for i in range(1, n):
	cudlr[i] = cudlr[i - 1] + max(0, cols[i - 1] - cols[i])
	cudrl[n - i - 1] = cudrl[n - i] + max(0, cols[n - i] - cols[n - i - 1])
for q in range(m):
	(s, t) = map(int, input().split())
	s -= 1
	t -= 1
	if s < t:
		print(cudlr[t] - cudlr[s])
	else:
		print(cudrl[t] - cudrl[s])


def solve(n, m, l, mat):
	res1 = [0] * (n + 1)
	k = 0
	for i in range(1, n):
		if l[i - 1] > l[i]:
			k += l[i - 1] - l[i]
		res1[i + 1] = k
	res2 = [0] * (n + 1)
	k = 0
	for i in range(n - 1, 0, -1):
		if l[i] > l[i - 1]:
			k += l[i] - l[i - 1]
		res2[i] = k
	for i in mat:
		if i[0] > i[1]:
			print(res2[i[1]] - res2[i[0]])
		else:
			print(res1[i[1]] - res1[i[0]])
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
mat = []
for i in range(m):
	(x, y) = map(int, input().split())
	mat.append([x, y])
solve(n, m, l, mat)


import sys
input = lambda : sys.stdin.readline().strip()
(a, b) = map(int, input().split())
m = list(map(int, input().split()))
dc = {1: 0}
dg = {a: 0}
l = []
r = []
for i in range(1, a):
	g = m[i - 1] - m[i]
	if g > 0:
		v = g
	else:
		v = 0
	dc[i + 1] = dc[i] + v
	l.append(v)
for i in range(a - 1, 0, -1):
	g = m[i] - m[i - 1]
	if g > 0:
		n = g
	else:
		n = 0
	dg[i] = dg[i + 1] + n
for _ in range(b):
	(x, y) = map(int, input().split())
	if x <= y:
		print(abs(dc[y] - dc[x]))
	else:
		print(abs(dg[x] - dg[y]))


def read_int() -> int:
	return int(input().strip())

def read_ints_map() -> map:
	return map(int, input().strip().split())

def read_ints_list() -> [int]:
	return [*read_ints_map()]
try:
	FIN = open('./input.txt')
except:
	FIN = open(0)
R = lambda : map(int, next(FIN).split())
(n, m) = R()
a = [*R()]
d_forward = [0] * n
d_backward = [0] * n
for i in range(n - 1):
	diff = a[i + 1] - a[i]
	d_forward[i + 1] = d_forward[i]
	if diff < 0:
		d_forward[i + 1] = d_forward[i] - diff
	else:
		d_forward[i + 1] = d_forward[i]
	j = n - 1 - i
	diff = a[j] - a[j - 1]
	d_backward[i + 1] = d_backward[i]
	if diff > 0:
		d_backward[i + 1] = d_backward[i] + diff
	else:
		d_backward[i + 1] = d_backward[i]
for _ in range(m):
	(s, t) = R()
	if s < t:
		(s, t) = (s - 1, t - 1)
		d = d_forward
	else:
		(s, t) = (n - s, n - t)
		d = d_backward
	print(d[t] - d[s])


def solve():
	(n, m) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	right = [0 for _ in range(n)]
	left = [0 for _ in range(n)]
	for i in range(n - 1):
		right[i + 1] = right[i] + max(a[i] - a[i + 1], 0)
	for i in range(n - 1, 0, -1):
		left[i - 1] = left[i] + max(a[i] - a[i - 1], 0)
	solution = [0 for _ in range(m)]
	for i in range(m):
		(p, q) = [int(x) for x in input().split()]
		if p < q:
			solution[i] = right[q - 1] - right[p - 1]
		else:
			solution[i] = left[q - 1] - left[p - 1]
	for sol in solution:
		print(sol)
solve()


arr1 = list(map(int, input().split()))
arr2 = list(map(int, input().split()))
arr3 = []
for i in range(arr1[1]):
	arr3.append(list(map(int, input().split())))
arr4 = []
arr5 = []
temp = arr2[0]
ans = 0
for i in arr2:
	if i < temp:
		ans += temp - i
	arr4.append(ans)
	temp = i
temp = arr2[len(arr2) - 1]
ans = 0
for i in range(len(arr2) - 1, -1, -1):
	if arr2[i] < temp:
		ans += temp - arr2[i]
	arr5.append(ans)
	temp = arr2[i]
arr5.sort(reverse=True)
for i in arr3:
	if i[0] < i[1]:
		print(arr4[i[1] - 1] - arr4[i[0] - 1])
	if i[0] > i[1]:
		print(arr5[i[1] - 1] - arr5[i[0] - 1])


from traceback import print_list
inputNM = list(map(int, input().split()))
n = inputNM[0]
m = inputNM[1]
a = list(map(int, input().split()))
s = list()
t = list()
for i in range(m):
	readST = list(map(int, input().split()))
	s.append(readST[0])
	t.append(readST[1])
increase = list()
sum = 0
increase.append(0)
for i in range(1, n):
	if a[i - 1] > a[i]:
		sum += a[i - 1] - a[i]
		increase.append(sum)
	else:
		increase.append(sum)
sum = 0
increase_ulta = list()
for i in range(n):
	increase_ulta.append(0)
for i in range(n - 2, -1, -1):
	if a[i] < a[i + 1]:
		sum += -a[i] + a[i + 1]
		increase_ulta[i] = sum
	else:
		increase_ulta[i] = sum
for i in range(m):
	if s[i] > t[i]:
		ans = -increase_ulta[s[i] - 1] + increase_ulta[t[i] - 1]
		print(ans)
	else:
		ans = increase[t[i] - 1] - increase[s[i] - 1]
		print(ans)


(n, m) = map(int, input().split())
mass = list(map(int, input().split()))
mass_2 = [0 for _ in range(n)]
mass_3 = [0 for _ in range(n)]
for i in range(1, n):
	mass_2[i] = mass_2[i - 1] + max(mass[i - 1] - mass[i], 0)
for i in range(n - 2, -1, -1):
	mass_3[i] = mass_3[i + 1] + max(mass[i + 1] - mass[i], 0)
s = ''
for _ in range(m):
	(p, q) = map(int, input().split())
	if p < q:
		s += str(mass_2[q - 1] - mass_2[p - 1])
	else:
		s += str(mass_3[q - 1] - mass_3[p - 1])
	s += '\n'
print(s[:-1])


import math
import collections
import itertools
import functools
(x, y) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
b = []
for _ in range(y):
	b.append(list(map(int, input().split(' '))))
pref = [0] * x
suff = [0] * x
for i in range(1, x):
	if a[i] < a[i - 1]:
		suff[i] = suff[i - 1] + a[i - 1] - a[i]
	else:
		suff[i] = suff[i - 1]
for i in range(1, x):
	if a[i] > a[i - 1]:
		pref[i] = pref[i - 1] + a[i] - a[i - 1]
	else:
		pref[i] = pref[i - 1]
for (i, j) in b:
	if i < j:
		print(suff[j - 1] - suff[i - 1])
	else:
		print(pref[i - 1] - pref[j - 1])


(n, m) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
q = []
for i in range(m):
	q.append(list(map(int, input().split(' '))))
b = [0]
for i in range(1, len(a)):
	if a[i - 1] >= a[i]:
		b.append(b[i - 1] + a[i - 1] - a[i])
	else:
		b.append(b[i - 1])
a.reverse()
c = [0]
for i in range(1, len(a)):
	if a[i - 1] >= a[i]:
		c.append(c[i - 1] + a[i - 1] - a[i])
	else:
		c.append(c[i - 1])
c.reverse()
for i in range(len(q)):
	if q[i][0] <= q[i][1]:
		print(b[q[i][1] - 1] - b[q[i][0] - 1])
	else:
		print(c[q[i][1] - 1] - c[q[i][0] - 1])


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
lst = []
for i in range(0, m):
	(x, y) = map(int, input().split())
	lst.append([x, y])
dp1 = [0 for i in range(0, n)]
dp2 = [0 for i in range(0, n)]
for i in range(1, n):
	if a[i] < a[i - 1]:
		dp1[i] = dp1[i - 1] + a[i - 1] - a[i]
	else:
		dp1[i] = dp1[i - 1]
for i in range(n - 2, -1, -1):
	if a[i + 1] > a[i]:
		dp2[i] = dp2[i + 1] + a[i + 1] - a[i]
	else:
		dp2[i] = dp2[i + 1]
for item in lst:
	if item[0] < item[1]:
		ans = dp1[item[1] - 1] - dp1[item[0] - 1]
	else:
		ans = dp2[item[1] - 1] - dp2[item[0] - 1]
	print(ans)


(n, m) = [int(i) for i in input().split()]
arr = [int(i) for i in input().split()]
quests = []
for _ in range(m):
	(s, t) = [int(i) for i in input().split()]
	quests.append((s, t))
cost_left = [0]
for i in range(0, len(arr) - 1):
	cost = arr[i] - arr[i + 1] if arr[i] > arr[i + 1] else 0
	cost_left.append(cost)
cost_right = [0]
for i in range(len(arr) - 2, -1, -1):
	cost = arr[i + 1] - arr[i] if arr[i + 1] > arr[i] else 0
	cost_right.append(cost)
cost_right = cost_right[::-1]
cumsum_left = []
curr = 0
for n in cost_left:
	cumsum_left.append(curr + n)
	curr = cumsum_left[-1]
cumsum_right = []
curr = 0
for n in cost_right[::-1]:
	cumsum_right.append(curr + n)
	curr = cumsum_right[-1]
cumsum_right = cumsum_right[::-1]
for q in quests:
	(s, t) = q
	if s < t:
		print(cumsum_left[t - 1] - cumsum_left[s - 1])
	else:
		print(cumsum_right[t - 1] - cumsum_right[s - 1])


(n, m) = map(int, input().split())
h = list(map(int, input().split()))
q = []
for i in range(m):
	q.append(list(map(int, input().split())))
fall_dmg = [0]
fall_dmg2 = [0]
for column in range(n - 1):
	fall_dmg.append(fall_dmg[column] + max(0, h[column] - h[column + 1]))
	fall_dmg2.append(fall_dmg2[column] + max(0, h[column + 1] - h[column]))
for i in q:
	(s, t) = (i[0], i[1])
	if s < t:
		dmg = fall_dmg[t - 1] - fall_dmg[s - 1]
	elif s > t:
		dmg = fall_dmg2[s - 1] - fall_dmg2[t - 1]
	print(dmg)


out = []
(n, m) = map(int, input().split())
a = [int(i) for i in input().split()]
pre = [0] * n
pst = [0] * n
for i in range(n - 1):
	pre[i + 1] = pre[i] + max(0, a[i] - a[i + 1])
	pst[n - i - 2] = pst[n - i - 1] + max(0, a[n - i - 1] - a[n - i - 2])
for j in range(m):
	(s, t) = map(int, input().split())
	s -= 1
	t -= 1
	ans = 0
	if t > s:
		ans = pre[t] - pre[s]
	else:
		ans = pst[t] - pst[s]
	out.append(ans)
for i in out:
	print(i)


(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
(l, r) = ([], [])
for p in range(m):
	(c, d) = list(map(int, input().split()))
	l.append(c)
	r.append(d)
(p, s) = ([0] * n, [0] * n)
(p[0], s[n - 1]) = (0, 0)
for i in range(1, n):
	if a[i] < a[i - 1]:
		p[i] = p[i - 1] + a[i - 1] - a[i]
	else:
		p[i] = p[i - 1]
for i in range(n - 2, -1, -1):
	if a[i] < a[i + 1]:
		s[i] = s[i + 1] + a[i + 1] - a[i]
	else:
		s[i] = s[i + 1]
for i in range(m):
	(a, b) = (r[i] - 1, l[i] - 1)
	if l[i] < r[i]:
		print(p[a] - p[b])
	else:
		print(s[a] - s[b])


(m, n) = map(int, input().split())
l1 = list(map(int, input().split()))
l2 = []
for i in range(n):
	l = list(map(int, input().split()))
	l2.append(l)
dp1 = [0]
dp2 = [0]
for i in range(1, len(l1)):
	if l1[i] < l1[i - 1]:
		dp1.append(dp1[i - 1] + l1[i - 1] - l1[i])
	else:
		dp1.append(dp1[i - 1])
for i in range(1, len(l1)):
	if l1[m - i] > l1[m - i - 1]:
		dp2.append(dp2[i - 1] + l1[m - i] - l1[m - i - 1])
	else:
		dp2.append(dp2[i - 1])
for i in range(n):
	x = l2[i][0]
	y = l2[i][1]
	sum = 0
	if y > x:
		print(dp1[y - 1] - dp1[x - 1])
	else:
		print(dp2[m - y] - dp2[m - x])


(n, m) = map(int, input().split())
x = list(map(int, input().split()))
y = []
for i in range(0, m):
	y.append(list(map(int, input().split())))
size = len(x)
a = [0] * n
dif = 0
add = 0
for f in range(1, size):
	add = add + max(0, x[f - 1] - x[f])
	a[f] = add
r = [0] * n
dif = 0
add = 0
for f in range(size - 2, -1, -1):
	add = add + max(0, x[f + 1] - x[f])
	r[f] = add
r.reverse()
for i in y:
	p = 0
	s = i[0]
	t = i[1]
	if s < t:
		p = a[t - 1] - a[s - 1]
	else:
		p = r[n - t] - r[n - s]
	print(p)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
q = []
for i in range(m):
	(aux1, aux2) = list(map(int, input().split()))
	q.append([aux1, aux2])
dp1 = []
dp2 = []
for i in range(n):
	dp1.append(0)
for i in range(1, n):
	if a[i] < a[i - 1]:
		dp1[i] = a[i - 1] - a[i]
	dp1[i] += dp1[i - 1]
for i in range(n):
	dp2.append(0)
for i in range(1, n):
	if a[i] > a[i - 1]:
		dp2[i] = a[i] - a[i - 1]
	dp2[i] += dp2[i - 1]
for par in q:
	if par[0] < par[1]:
		print(dp1[par[1] - 1] - dp1[par[0] - 1])
	else:
		print(dp2[par[0] - 1] - dp2[par[1] - 1])


tn__ = [int(i) for i in list(input().split(' '))]
htLst = [int(i) for i in list(input().split(' '))]
qstLst = []
for i in range(0, tn__[1]):
	mv = [int(i) for i in list(input().split(' '))]
	qstLst.append(mv)
htLst__1 = [0]
for i in range(0, len(htLst) - 1):
	x = (htLst[i] - htLst[i + 1], 0)[htLst[i] < htLst[i + 1]]
	htLst__1.append(htLst__1[i] + x)
htLst__2 = [0] * (len(htLst) + 1)
for i in range(len(htLst) - 1, 0, -1):
	x = (0, htLst[i] - htLst[i - 1])[htLst[i] > htLst[i - 1]]
	htLst__2[i] = htLst__2[i + 1] + x
for i in qstLst:
	if i[0] < i[1]:
		x = htLst__1[i[1] - 1] - htLst__1[i[0] - 1]
	else:
		x = htLst__2[i[1]] - htLst__2[i[0]]
	print(x)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
l = []
d = dict()
for _ in range(k):
	(x, y) = map(int, input().split())
	l.append([x, y])
d[0] = 0
count = 0
d1 = dict()
d1[n - 1] = 0
count1 = 0
for i in range(1, len(a)):
	if a[i] < a[i - 1]:
		count += a[i - 1] - a[i]
		d[i] = count
	else:
		d[i] = count
for i in range(len(a) - 2, -1, -1):
	if a[i] < a[i + 1]:
		count1 += a[i + 1] - a[i]
		d1[i] = count1
	else:
		d1[i] = count1
for i in range(len(l)):
	if l[i][0] <= l[i][1]:
		x = d[l[i][0] - 1]
		y = d[l[i][1] - 1]
		print(y - x)
	else:
		x = d1[l[i][0] - 1]
		y = d1[l[i][1] - 1]
		print(y - x)


def inp_a():
	return [int(x) for x in input().split()]

def inp_s(k):
	arr = []
	for i in range(k):
		arr.append(inp_a())
	return arr

def help(s, t):
	if s < t:
		return forward[t] - forward[s]
	else:
		return backward[t - 1] - backward[s - 1]
(n, m) = inp_a()
a = inp_a()
quest = inp_s(m)
forward = [0, 0]
backward = []
for i in range(1, n):
	if a[i] < a[i - 1]:
		forward.append(a[i - 1] - a[i])
		backward.append(0)
	else:
		backward.append(abs(a[i - 1] - a[i]))
		forward.append(0)
backward.append(0)
for i in range(1, n + 1):
	forward[i] += forward[i - 1]
for i in range(n - 2, -1, -1):
	backward[i] += backward[i + 1]
for i in range(m):
	print(help(quest[i][0], quest[i][1]))


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
quests = [list(map(int, input().split())) for x in range(m)]
dmg = [0 for i in range(n)]
for x in range(1, n):
	dmg[x] += dmg[x - 1]
	if a[x] < a[x - 1]:
		dmg[x] += a[x - 1] - a[x]
revDmg = [0 for i in range(n)]
for x in range(n - 2, -1, -1):
	revDmg[x] += revDmg[x + 1]
	if a[x] < a[x + 1]:
		revDmg[x] += a[x + 1] - a[x]
for quest in quests:
	if quest[0] <= quest[1]:
		print(dmg[quest[1] - 1] - dmg[quest[0] - 1])
	else:
		print(revDmg[quest[1] - 1] - revDmg[quest[0] - 1])


from collections import deque
from sys import stdin

def test(problem):
	pass

def solve(n, b, l):
	t1 = deque()
	t2 = deque()
	t1.append(0)
	t2.append(0)
	for i in range(1, n):
		t1.append(max(l[i - 1] - l[i], 0) + t1[-1])
	for i in range(n - 1, 0, -1):
		t2.insert(0, max(l[i] - l[i - 1], 0) + t2[0])
	for i in range(b):
		(k, h) = list((int(i) for i in stdin.readline().split()))
		if k < h:
			print(t1[h - 1] - t1[k - 1])
		else:
			print(t2[h - 1] - t2[k - 1])
(n, b) = list((int(i) for i in stdin.readline().split()))
l = list((int(i) for i in stdin.readline().split()))
solve(n, b, l)


def main():
	(n, m) = map(int, input().split())
	world_map = [int(num) for num in input().split()]
	pos_positive = [0] * n
	sum = 0
	for i in range(1, n):
		if world_map[i] < world_map[i - 1]:
			sum += world_map[i - 1] - world_map[i]
			pos_positive[i] = sum
		else:
			pos_positive[i] = sum
	for l in range(m):
		(i, j) = map(int, input().split())
		if i > j:
			sum = pos_positive[i - 1] - pos_positive[j - 1]
			sum = world_map[j - 1] - world_map[i - 1] - sum
			sum = -sum
		else:
			sum = pos_positive[j - 1] - pos_positive[i - 1]
		print(sum)
main()


def resi():
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	fd0 = [0] * n
	fd1 = [0] * n
	for i in range(1, n):
		fd0[i] = fd0[i - 1] + max(0, a[i - 1] - a[i])
	for i in reversed(range(n - 1)):
		fd1[i] = fd1[i + 1] + max(0, a[i + 1] - a[i])
	for i in range(m):
		(s, t) = map(int, input().split())
		if s < t:
			print(fd0[t - 1] - fd0[s - 1])
		else:
			print(fd1[t - 1] - fd1[s - 1])
resi()


import sys
import collections
from math import ceil, gcd, sqrt, log
import bisect
INF = float('inf')
mod = 1000000007

def solve():
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))[:n]
	pref = [0] * n
	suff = [0] * n
	for i in range(1, n):
		if A[i] > A[i - 1]:
			pref[i] = pref[i - 1]
		else:
			pref[i] += pref[i - 1] + (A[i - 1] - A[i])
	for j in range(n - 2, -1, -1):
		if A[j] > A[j + 1]:
			suff[j] = suff[j + 1]
		else:
			suff[j] += suff[j + 1] + (A[j + 1] - A[j])
	for i in range(m):
		(a, b) = map(int, input().split())
		if b > a:
			print(pref[b - 1] - pref[a - 1])
		else:
			print(suff[b - 1] - suff[a - 1])
t = 1
while t != 0:
	solve()
	t -= 1


def main():
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	accum1 = [0, 0]
	accum2 = [0, 0]
	for i in range(1, n):
		if A[i] < A[i - 1]:
			accum1.append(accum1[-1] + A[i - 1] - A[i])
		else:
			accum1.append(accum1[-1])
		if A[n - 1 - i] < A[n - 1 - i + 1]:
			accum2.append(accum2[-1] + A[n - 1 - i + 1] - A[n - 1 - i])
		else:
			accum2.append(accum2[-1])
	for i in range(m):
		(s, t) = map(int, input().split())
		s -= 1
		t -= 1
		ans = 0
		if s < t:
			ans = accum1[t + 1] - accum1[s + 1]
		else:
			ans = accum2[n - 1 - (t - 1)] - accum2[n - 1 - (s - 1)]
		print(ans)
main()


(aa, bb) = map(int, input().split())
a = list(map(int, input().split()))
z = [0]
x = [0]
for i in range(aa - 1):
	if a[i + 1] < a[i]:
		z.append(a[i] - a[i + 1] + z[-1])
		x.append(0 + x[-1])
	else:
		x.append(a[i + 1] - a[i] + x[-1])
		z.append(0 + z[-1])
for _ in range(bb):
	(b, c) = map(int, input().split())
	if b < c:
		print(-z[b - 1] + z[c - 1])
	else:
		print(-x[c - 1] + x[b - 1])


(n, m) = map(int, input().split())
ls = list(map(int, input().split()))
damagef = [0]
damaged = [0 for i in range(n)]
a = 0
for i in range(1, n):
	if ls[i] < ls[i - 1]:
		a += ls[i - 1] - ls[i]
	damagef.append(a)
a = 0
for i in range(n - 1, 0, -1):
	if ls[i] > ls[i - 1]:
		a += ls[i] - ls[i - 1]
	damaged[i - 1] = a
for i in range(m):
	(s, t) = map(int, input().split())
	if t > s:
		print(damagef[t - 1] - damagef[s - 1])
	else:
		print(damaged[t - 1] - damaged[s - 1])


(k, n) = map(int, input().split())
arr = list(map(int, input().split()))
brr = [0]
crr = []
ans = 0
for i in range(k - 1):
	if arr[i + 1] < arr[i]:
		ans += arr[i] - arr[i + 1]
		brr.append(ans)
	else:
		brr.append(ans)
trr = arr.copy()
trr.reverse()
ans = 0
for i in range(k - 1):
	if trr[i + 1] < trr[i]:
		ans += trr[i] - trr[i + 1]
		crr.append(ans)
	else:
		crr.append(ans)
crr.reverse()
crr.append(0)
for j in range(n):
	(a, b) = map(int, input().split())
	if a <= b:
		print(brr[b - 1] - brr[a - 1])
	else:
		print(crr[b - 1] - crr[a - 1])


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
k = 0
l2 = [0]
l3 = [0]
for i in range(1, n):
	if l[i] < l[i - 1]:
		k += l[i - 1] - l[i]
	l2.append(k)
k = 0
for i in range(n - 1, 0, -1):
	if l[i] > l[i - 1]:
		k += l[i] - l[i - 1]
	l3.append(k)
l4 = [l3[i] for i in range(n - 1, -1, -1)]
for _ in range(m):
	(s, t) = map(int, input().split())
	if s < t:
		print(l2[t - 1] - l2[s - 1])
	else:
		print(l4[t - 1] - l4[s - 1])


(n, m) = map(int, input().split())
a = [int(i) for i in input().split()]
lr = [0]
rl = [0]
for i in range(n - 1):
	if a[i] > a[i + 1]:
		lr.append(lr[i] + a[i] - a[i + 1])
		rl.append(rl[i])
	elif a[i] < a[i + 1]:
		lr.append(lr[i])
		rl.append(rl[i] + a[i + 1] - a[i])
	else:
		lr.append(lr[i])
		rl.append(rl[i])
for _ in range(m):
	(s, t) = map(int, input().split())
	if s > t:
		print(rl[s - 1] - rl[t - 1])
	else:
		print(lr[t - 1] - lr[s - 1])


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
inc = [0]
cost = 0
for i in range(1, n):
	if a[i] < a[i - 1]:
		cost += a[i - 1] - a[i]
	inc.append(cost)
dec = [0 for i in range(n)]
cost = 0
for i in range(n - 2, -1, -1):
	if a[i] < a[i + 1]:
		cost += a[i + 1] - a[i]
	dec[i] = cost
for _ in range(m):
	(s, t) = map(int, input().split())
	if s <= t:
		print(inc[t - 1] - inc[s - 1])
	else:
		print(dec[t - 1] - dec[s - 1])


from itertools import accumulate
(n, m) = list(map(int, input().split()))
A = list(map(int, input().split()))
diff = [x - y for (x, y) in zip(A[:-1], A[1:])]
left_falls = [0] + list(accumulate((x if x > 0 else 0 for x in diff)))
right_falls = right_falls = [0] + list(accumulate((-x if x < 0 else 0 for x in diff)))
for _ in range(m):
	(s, t) = list(map(int, input().split()))
	if s < t:
		cost = left_falls[t - 1] - left_falls[s - 1]
	else:
		cost = right_falls[s - 1] - right_falls[t - 1]
	print(cost)


(n, m) = map(int, input().split())
h = list(map(int, input().split()))
pref_f = [0] * n
pref_b = [0] * n
for i in range(n - 1):
	d = h[i] - h[i + 1]
	if d > 0:
		pref_f[i + 1] = d
	else:
		pref_b[i + 1] = -d
	pref_f[i + 1] += pref_f[i]
	pref_b[i + 1] += pref_b[i]
for _ in range(m):
	(s, t) = map(int, input().split())
	if s < t:
		print(pref_f[t - 1] - pref_f[s - 1])
	else:
		print(pref_b[s - 1] - pref_b[t - 1])


def main():
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [0 for i in range(n)]
	c = [0 for i in range(n)]
	for i in range(1, n):
		if a[i] < a[i - 1]:
			b[i] = a[i - 1] - a[i]
	for i in range(n - 2, -1, -1):
		if a[i] < a[i + 1]:
			c[i] = a[i + 1] - a[i]
	for i in range(1, n):
		b[i] += b[i - 1]
	for i in range(n - 2, -1, -1):
		c[i] += c[i + 1]
	for i in range(m):
		(s, t) = map(int, input().split())
		if s < t:
			print(b[t - 1] - b[s - 1])
		else:
			print(c[t - 1] - c[s - 1])
main()


(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
dp = [0]
for i in range(1, n):
	if arr[i - 1] > arr[i]:
		dp.append(dp[i - 1] + arr[i - 1] - arr[i])
	else:
		dp.append(dp[i - 1])
dpp = [0]
j = 1
for i in range(n - 2, -1, -1):
	if arr[i + 1] > arr[i]:
		dpp.append(dpp[j - 1] + arr[i + 1] - arr[i])
	else:
		dpp.append(dpp[j - 1])
	j += 1
dpp = dpp[::-1]
for i in range(m):
	(s, t) = map(int, input().split())
	if s < t:
		print(dp[t - 1] - dp[s - 1])
	else:
		print(dpp[t - 1] - dpp[s - 1])


(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
diff = [0]
rev_diff = [0]
for i in range(1, n):
	if arr[i - 1] - arr[i] > 0:
		diff.append(diff[i - 1] + (arr[i - 1] - arr[i]))
		rev_diff.append(rev_diff[i - 1])
	else:
		diff.append(diff[i - 1])
		rev_diff.append(rev_diff[i - 1] + (arr[i] - arr[i - 1]))
for _ in range(m):
	(s, t) = map(int, input().split())
	if s < t:
		res = diff[t - 1] - diff[s - 1]
		print(res)
	else:
		res = rev_diff[s - 1] - rev_diff[t - 1]
		print(res)


try:
	(n, k2) = map(int, input().split(' '))
	l = list(map(int, input().split(' ')))
	k = [0 for i in range(n)]
	k1 = [0 for j in range(n)]
	pr = l[0]
	for i in range(1, n):
		if l[i] < pr:
			k[i] = k[i - 1] + pr - l[i]
		else:
			k[i] = k[i - 1]
		pr = l[i]
	pr = l[n - 1]
	for i in range(n - 2, -1, -1):
		if pr > l[i]:
			k1[i] = k1[i + 1] + pr - l[i]
		else:
			k1[i] = k1[i + 1]
		pr = l[i]
	for i in range(k2):
		(a, b) = map(int, input().split(' '))
		a = a - 1
		b = b - 1
		if a <= b:
			print(k[b] - k[a])
		else:
			print(k1[b] - k1[a])
except:
	pass


(n, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
p = 0
q = 0
l1 = [0]
l2 = [0]
for i in range(1, n):
	if a[i - 1] > a[i]:
		p += a[i - 1] - a[i]
	l1.append(p)
for i in range(n - 1, 0, -1):
	if a[i - 1] < a[i]:
		q += a[i] - a[i - 1]
	l2.append(q)
l2 = l2[::-1]
for _ in range(m):
	(s, t) = [int(i) for i in input().split()]
	if s < t:
		print(l1[t - 1] - l1[s - 1])
	else:
		print(l2[t - 1] - l2[s - 1])


(n, m) = map(int, input().split())
x = list(map(int, input().split()))
y = [0] * n
z = [0] * n
sum1 = 0
sum2 = 0
for j in range(1, n):
	if x[j - 1] > x[j]:
		sum1 += x[j - 1] - x[j]
		y[j] = sum1
		z[j] = sum2
	else:
		y[j] = sum1
		sum2 += x[j] - x[j - 1]
		z[j] = sum2
for j in range(m):
	count = 0
	(s, t) = map(int, input().split())
	if s < t:
		print(y[t - 1] - y[s - 1])
	elif s > t:
		print(z[s - 1] - z[t - 1])
	else:
		print(0)


(a, b) = map(int, input().split())
l = list(map(int, input().split()))
li1 = [0]
li2 = [0]
for i in range(a - 1):
	li1.append(li1[i] + max(0, l[i] - l[i + 1]))
	li2.append(li2[i] + max(0, l[i + 1] - l[i]))
for i in range(b):
	(x, y) = map(int, input().split())
	if x < y:
		print(li1[y - 1] - li1[x - 1])
	else:
		print(li2[x - 1] - li2[y - 1])


count_of_pairs = input().split()
count_of_pairs = int(count_of_pairs[-1])
world = [int(i) for i in input().split()]
prefleft = [0] * (len(world) + 1)
prefright = [0] * len(prefleft)
for i in range(1, len(world)):
	if world[i] < world[i - 1]:
		prefleft[i + 1] = prefleft[i] + world[i - 1] - world[i]
	else:
		prefleft[i + 1] = prefleft[i]
	if world[-i - 1] < world[-i]:
		prefright[i + 1] = prefright[i] + world[-i] - world[-i - 1]
	else:
		prefright[i + 1] = prefright[i]
for i in range(count_of_pairs):
	(start, end) = input().split()
	(start, end) = (int(start), int(end))
	if start < end:
		print(prefleft[end] - prefleft[start])
	else:
		print(prefright[-end] - prefright[-start])


inputs = [int(num) for num in input().split()]
n = inputs[0]
m = inputs[1]
list1 = [int(num) for num in input().split()]
psum = [0, 0]
for i in range(1, n):
	if list1[i] < list1[i - 1]:
		psum.append(psum[i] + list1[i - 1] - list1[i])
	else:
		psum.append(psum[i])
psum2 = [0 for i in range(0, n + 1)]
for i in range(n - 2, -1, -1):
	if list1[i] < list1[i + 1]:
		psum2[i] = psum2[i + 1] + list1[i + 1] - list1[i]
	else:
		psum2[i] = psum2[i + 1]
for i in range(0, m):
	inputs1 = [int(num) for num in input().split()]
	if inputs1[1] >= inputs1[0]:
		print(psum[inputs1[1]] - psum[inputs1[0]])
	else:
		print(psum2[inputs1[1] - 1] - psum2[inputs1[0] - 1])


(n, q) = map(int, input().split())
a = list(map(int, input().split()))
left = [0]
for i in range(1, n):
	if a[i] < a[i - 1]:
		left.append(left[-1] + a[i - 1] - a[i])
	else:
		left.append(left[-1])
right = [0]
for i in range(n - 2, -1, -1):
	if a[i] < a[i + 1]:
		right.append(a[i + 1] - a[i] + right[-1])
	else:
		right.append(right[-1])
right = right[::-1]
for _ in range(q):
	(i, j) = map(int, input().split())
	if i < j:
		print(left[j - 1] - left[i - 1])
	else:
		print(right[j - 1] - right[i - 1])


(n, m) = input().split(' ')
(n, m) = (int(n), int(m))
a = input().split(' ')
a = list(map(int, a))
lr = []
rl = []
for i in range(n - 1):
	if a[i] > a[i + 1]:
		lr.append(a[i] - a[i + 1])
		rl.append(0)
	else:
		lr.append(0)
		rl.append(a[i + 1] - a[i])
sum_lr = [0]
sum_rl = [0]
for i in range(len(lr)):
	sum_lr.append(sum_lr[i] + lr[i])
for i in range(len(rl)):
	sum_rl.append(sum_rl[i] + rl[i])
for _ in range(m):
	(s, t) = input().split(' ')
	(s, t) = (int(s), int(t))
	if s < t:
		print(sum_lr[t - 1] - sum_lr[s - 1])
	else:
		print(sum_rl[s - 1] - sum_rl[t - 1])


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
u = [0]
d = [0]
for i in range(1, len(l)):
	if l[i - 1] > l[i]:
		u.append(l[i - 1] - l[i] + u[-1])
	else:
		u.append(u[-1])
	if l[i] > l[i - 1]:
		d.append(l[i] - l[i - 1] + d[-1])
	else:
		d.append(d[-1])
for i in range(m):
	(s, e) = map(int, input().split())
	if s < e:
		print(u[e - 1] - u[s - 1])
	else:
		print(d[s - 1] - d[e - 1])


(n, m) = map(int, input().split())
List = list(map(int, input().split()))
rightarray = [0]
leftarray = [0]
damage = 0
for i in range(0, n - 1, +1):
	if List[i] > List[i + 1]:
		damage += List[i] - List[i + 1]
	rightarray.append(damage)
damage = 0
for i in range(n - 1, 0, -1):
	if List[i] > List[i - 1]:
		damage += List[i] - List[i - 1]
	leftarray.append(damage)
leftarray.reverse()
for i in range(m):
	(s, t) = map(int, input().split())
	damage = 0
	if s > t:
		damage = leftarray[t - 1] - leftarray[s - 1]
	else:
		damage = rightarray[t - 1] - rightarray[s - 1]
	print(damage)


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
l1 = [0]
l2 = [0]
for i in range(n - 1, 0, -1):
	o = l[i] - l[i - 1]
	if o < 0:
		o = 0
	l2.append(l2[-1] + o)
for i in range(n - 1):
	o = l[i] - l[i + 1]
	if o < 0:
		o = 0
	l1.append(l1[-1] + o)
for i in range(m):
	(x, y) = map(int, input().split())
	if x > y:
		print(abs(l2[n - x] - l2[n - y]))
	else:
		print(abs(l1[y - 1] - l1[x - 1]))


(n, m) = map(int, input().split())
a = [int(aj) for aj in input().split()]
(p, s) = ([0] * n, [0] * n)
for j in range(n):
	p[j] = p[j - 1] + (a[j - 1] - a[j] if a[j] < a[j - 1] else 0) if j - 1 > -1 else 0
for j in range(-1, -n - 1, -1):
	s[j] = s[j + 1] + (a[j + 1] - a[j] if a[j] < a[j + 1] else 0) if j + 1 < 0 else 0
for i in range(m):
	(start, finish) = map(int, input().split())
	print(p[finish - 1] - p[start - 1] if finish > start else s[finish - 1] - s[start - 1])


(n, m) = map(int, input().split())
lst = list(map(int, input().split()))
lst_r = [0]
lst_l = [0]
for x in range(n - 1):
	q = lst[x] - lst[x + 1]
	if q > 0:
		lst_r.append(lst_r[-1] + q)
		lst_l.append(lst_l[-1])
	elif q < 0:
		lst_l.append(lst_l[-1] - q)
		lst_r.append(lst_r[-1])
	else:
		lst_r.append(lst_r[-1])
		lst_l.append(lst_l[-1])
for x in range(m):
	(a, b) = map(int, input().split())
	if a < b:
		print(lst_r[b - 1] - lst_r[a - 1])
	else:
		print(lst_l[a - 1] - lst_l[b - 1])


(n, m) = map(int, input().split())
c = [int(i) for i in input().split()]
f = [0] * n
g = [0] * n
for i in range(1, n):
	f[i] = f[i - 1] + max(0, c[i - 1] - c[i])
	g[-i - 1] = g[-i] + max(0, c[-i] - c[-i - 1])
for i in range(m):
	(x, y) = map(int, input().split())
	if x < y:
		print(f[y - 1] - f[x - 1])
	else:
		print(g[y - 1] - g[x - 1])


def solve():
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	pref = [0]
	prefrev = [0]
	for i in range(1, n):
		pref.append(max(0, a[i - 1] - a[i]) + pref[-1])
	a.reverse()
	for i in range(1, n):
		prefrev.append(max(0, a[i - 1] - a[i]) + prefrev[-1])
	prefrev.reverse()
	a.reverse()
	for i in range(m):
		(s, t) = list(map(int, input().split()))
		if s <= t:
			print(pref[t - 1] - pref[s - 1])
		else:
			print(-(prefrev[s - 1] - prefrev[t - 1]))
nnnn = 1
while nnnn:
	nnnn -= 1
	solve()


(n, m) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
a = [0]
for i in range(1, n):
	if arr[i] < arr[i - 1]:
		a.append(a[-1] + arr[i - 1] - arr[i])
	else:
		a.append(a[-1])
b = [0]
for i in reversed(range(n - 1)):
	if arr[i] < arr[i + 1]:
		b.append(b[-1] + arr[i + 1] - arr[i])
	else:
		b.append(b[-1])
b = b[::-1]
for q in range(m):
	(x, y) = [int(x) for x in input().split()]
	if x < y:
		print(a[y - 1] - a[x - 1])
	else:
		print(b[y - 1] - b[x - 1])


(n, m) = map(int, input().split(' '))
lst = list(map(int, input().split(' ')))
lst1 = [0]
lst2 = [0]
cnt = 0
for i in range(1, n):
	if lst[i] < lst[i - 1]:
		cnt += lst[i - 1] - lst[i]
	lst1.append(cnt)
cnt = 0
for i in range(2, n + 1):
	if lst[-i] < lst[-i + 1]:
		cnt += lst[-i + 1] - lst[-i]
	lst2.append(cnt)
lst2.reverse()
for i in range(m):
	(x, y) = map(int, input().split(' '))
	if y >= x:
		print(lst1[y - 1] - lst1[x - 1])
	else:
		print(lst2[y - 1] - lst2[x - 1])


(x, y) = input().split()
x = int(x)
y = int(y)
z = list(map(int, input().split()))
m = []
m1 = []
m1.append(0)
m.append(0)
for i in range(x - 1):
	if z[i + 1] < z[i]:
		m.append(m[i] - (z[i] - z[i + 1]))
	else:
		m.append(m[i])
z.reverse()
for i in range(x - 1):
	if z[i + 1] < z[i]:
		m1.append(m1[i] - (z[i] - z[i + 1]))
	else:
		m1.append(m1[i])
for i in range(y):
	(a, b) = input().split()
	a = int(a)
	b = int(b)
	if a < b:
		print(m[a - 1] - m[b - 1])
	else:
		print(m1[-a] - m1[-b])


(n, m) = map(int, input().split())
a = [int(i) for i in input().split()]
pre = [0] * n
suff = [0] * n
for i in range(1, n):
	if a[i] < a[i - 1]:
		pre[i] = pre[i - 1] + a[i - 1] - a[i]
	else:
		pre[i] = pre[i - 1]
for i in range(n - 2, -1, -1):
	if a[i] < a[i + 1]:
		suff[i] = suff[i + 1] + a[i + 1] - a[i]
	else:
		suff[i] = suff[i + 1]
for i in range(m):
	ans = 0
	(x, y) = map(int, input().split())
	if x < y:
		print(pre[y - 1] - pre[x - 1])
	else:
		print(suff[y - 1] - suff[x - 1])


def test():
	(n, m) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	f = [0]
	b = [0]
	for i in range(1, n):
		if a[i] < a[i - 1]:
			f.append(f[i - 1] + a[i - 1] - a[i])
		else:
			f.append(f[i - 1])
	a.reverse()
	for i in range(1, n):
		if a[i] < a[i - 1]:
			b.append(b[i - 1] + a[i - 1] - a[i])
		else:
			b.append(b[i - 1])
	b.reverse()
	for i in range(m):
		(x, y) = [int(i) for i in input().split()]
		x -= 1
		y -= 1
		if x < y:
			print(f[y] - f[x])
		else:
			print(b[y] - b[x])
	return
t = 1
for i in range(t):
	test()


R = lambda : map(int, input().split())
(n, m) = R()
(*c,) = R()
b = [[0], [0]]
f = max
for x in b:
	for (u, v) in zip([0] + c, c):
		x += (x[-1] + f(0, u - v),)
	f = min
for _ in [0] * m:
	(s, t) = R()
	l = b[s > t]
	print(l[t] - l[s])


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
(suffix, prefix) = ([0], [0])
for i in range(n - 1):
	if a[i] > a[i + 1]:
		prefix.append(a[i] - a[i + 1])
		suffix.append(0)
	else:
		prefix.append(0)
		suffix.append(a[i + 1] - a[i])
	prefix[i + 1] += prefix[i]
	suffix[i + 1] += suffix[i]
for _ in range(m):
	(s, t) = map(int, input().split())
	if s < t:
		print(prefix[t - 1] - prefix[s - 1])
	else:
		print(suffix[s - 1] - suffix[t - 1])


data = input().split()
cols = int(data[0])
quests = int(data[1])
colsdata = input().split()
for i in range(len(colsdata)):
	colsdata[i] = int(colsdata[i])
colsdata.insert(0, 0)
forwardprefixSum = [0]
for i in range(1, len(colsdata)):
	if colsdata[i] < colsdata[i - 1]:
		forwardprefixSum.append(forwardprefixSum[i - 1] + (colsdata[i - 1] - colsdata[i]))
	else:
		forwardprefixSum.append(forwardprefixSum[i - 1])
colsdata.pop(0)
colsdata.reverse()
colsdata.insert(0, 0)
backwardprefixSum = [0]
for i in range(1, len(colsdata)):
	if colsdata[i] < colsdata[i - 1]:
		backwardprefixSum.append(backwardprefixSum[i - 1] + (colsdata[i - 1] - colsdata[i]))
	else:
		backwardprefixSum.append(backwardprefixSum[i - 1])
for i in range(quests):
	quest = input().split()
	start = int(quest[0])
	end = int(quest[1])
	if end >= start:
		print(forwardprefixSum[end] - forwardprefixSum[start])
	else:
		print(backwardprefixSum[len(backwardprefixSum) - end] - backwardprefixSum[len(backwardprefixSum) - start])


import sys
import threading
from functools import lru_cache
from bisect import bisect_left
import math
from collections import defaultdict, deque
from heapq import *

def main():
	(n, m) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	forward = [0]
	for index in range(1, n):
		if a[index] <= a[index - 1]:
			forward.append(a[index - 1] - a[index] + forward[-1])
		else:
			forward.append(forward[-1])
	backward = [0]
	for index in range(n - 2, -1, -1):
		if a[index] <= a[index + 1]:
			backward.append(a[index + 1] - a[index] + backward[-1])
		else:
			backward.append(backward[-1])
	backward.reverse()
	for _ in range(m):
		(left, right) = [int(i) - 1 for i in input().split()]
		if right > left:
			print(forward[right] - forward[left])
		else:
			print(backward[right] - backward[left])
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
less = [0]
for i in range(1, n):
	if l[i] > l[i - 1]:
		less.append(0 + less[-1])
	else:
		less.append(l[i - 1] - l[i] + less[-1])
gre = [0]
for i in range(n - 1, 0, -1):
	if l[i] > l[i - 1]:
		gre.append(l[i] - l[i - 1] + gre[-1])
	else:
		gre.append(0 + gre[-1])
gre.reverse()
for i in range(m):
	(x, y) = map(int, input().split())
	if x < y:
		print(less[y - 1] - less[x - 1])
	else:
		print(gre[y - 1] - gre[x - 1])


def meow(l, n):
	mo = [0]
	i = 1
	coun = 0
	while i < n:
		if l[i] < l[i - 1]:
			coun = coun + l[i - 1] - l[i]
		mo.append(coun)
		i = i + 1
	return mo

def meowBack(l, n):
	wo = [0]
	i = n - 2
	cou = 0
	while i > -1:
		if l[i] < l[i + 1]:
			cou = cou + l[i + 1] - l[i]
		wo.append(cou)
		i = i - 1
	return wo[::-1]
z = list(map(int, input().split()))
l = list(map(int, input().split()))
n = z[0]
m = z[1]
meo = meow(l, n)
weo = meowBack(l, n)
k = 0
while k < m:
	o = list(map(int, input().split()))
	if o[0] < o[1]:
		print(meo[o[1] - 1] - meo[o[0] - 1])
	else:
		print(weo[o[1] - 1] - weo[o[0] - 1])
	k = k + 1


(n, m) = [int(x) for x in input().split()]
l = [int(x) for x in input().split()]
prefix = [0] * len(l)
suffix = [0] * len(l)
for i in range(1, len(l)):
	if l[i] >= l[i - 1]:
		prefix[i] = prefix[i - 1]
	else:
		prefix[i] = prefix[i - 1] + l[i - 1] - l[i]
for i in range(len(l) - 2, -1, -1):
	if l[i] >= l[i + 1]:
		suffix[i] = suffix[i + 1]
	else:
		suffix[i] = suffix[i + 1] + l[i + 1] - l[i]
for i in range(m):
	(a, b) = [int(x) for x in input().split()]
	if a < b:
		print(prefix[b - 1] - prefix[a - 1])
	else:
		print(suffix[b - 1] - suffix[a - 1])
print()


(a, b) = map(int, input().split())
c = list(map(int, input().split()))
e = [0, 0]
d = []
if c[0] > c[1]:
	e.append(c[0] - c[1])
else:
	e.append(0)
for i in range(1, a - 1):
	if c[i] > c[i + 1]:
		e.append(e[-1] + c[i] - c[i + 1])
	else:
		e.append(e[-1])
c = c[::-1]
if c[0] > c[1]:
	d.append(c[0] - c[1])
else:
	d.append(0)
for i in range(1, a - 1):
	if c[i] > c[i + 1]:
		d.append(d[-1] + c[i] - c[i + 1])
	else:
		d.append(d[-1])
d.append(0)
d = d[::-1]
d.append(0)
for i in range(b):
	(f, g) = map(int, input().split())
	if f > g:
		print(d[g] - d[f])
	else:
		print(e[g] - e[f])


for t in range(1):
	(n, m) = map(int, input().split())
	plan = [0] * (n + 1)
	flag = [0] * (n + 1)
	arr = list(map(int, input().split()))
	for i in range(1, len(arr)):
		if arr[i - 1] >= arr[i]:
			plan[i] = plan[i - 1] + (arr[i - 1] - arr[i])
		else:
			plan[i] = plan[i - 1]
	for i in range(len(arr) - 2, -1, -1):
		if arr[i + 1] >= arr[i]:
			flag[i] = flag[i + 1] + (arr[i + 1] - arr[i])
		else:
			flag[i] = flag[i + 1]
	for i in range(m):
		(a, b) = map(int, input().split())
		if a <= b:
			print(plan[b - 1] - plan[a - 1])
		else:
			print(flag[b - 1] - flag[a - 1])


(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
lenn = len(arr)
a = [0]
b = [0]
suma = 0
for i in range(1, lenn):
	if arr[i] < arr[i - 1]:
		suma += abs(arr[i - 1] - arr[i])
		a.append(suma)
	else:
		a.append(suma)
sumb = 0
j = lenn
while j > 1:
	if arr[j - 1] > arr[j - 2]:
		sumb += abs(arr[j - 1] - arr[j - 2])
		b.append(sumb)
	else:
		b.append(sumb)
	j = j - 1
for i in range(m):
	(s, t) = map(int, input().split())
	if t > s:
		min = a[t - 1] - a[s - 1]
		print(min)
	elif t == s:
		print(0)
	else:
		min = b[lenn - t] - b[lenn - s]
		print(min)


(n, m) = map(int, input().split())
a = [0] + list(map(int, input().split()))
sums = [0]
sums2 = [0]
for i in range(1, n):
	sums.append(max(a[i] - a[i + 1], 0) + sums[-1])
	sums2.append(max(a[i + 1] - a[i], 0) + sums2[-1])
for _ in range(m):
	damage = 0
	(s, t) = map(int, input().split())
	if s < t:
		damage = sums[t - 1] - sums[s - 1]
	else:
		damage = sums2[s - 1] - sums2[t - 1]
	print(damage)


(n, m) = input().split()
(n, m) = (int(n), int(m))
As = input().split()
As = [int(_) for _ in As]
prefix_sums = [0]
for i in range(n - 1):
	value = 0 if As[i + 1] >= As[i] else As[i] - As[i + 1]
	prefix_sums.append(prefix_sums[-1] + value)
postfix_sums = [0]
for i in range(n - 1, 0, -1):
	value = 0 if As[i - 1] >= As[i] else As[i] - As[i - 1]
	postfix_sums.append(postfix_sums[-1] + value)
for _ in range(m):
	(s, t) = input().split()
	(s, t) = (int(s) - 1, int(t) - 1)
	if s < t:
		print(prefix_sums[t] - prefix_sums[s])
	else:
		print(postfix_sums[n - 1 - t] - postfix_sums[n - 1 - s])


(n, m) = map(int, input().split())
a = [int(i) for i in input().split()]
l = [0]
r = [0]
for i in range(0, n - 1):
	if a[i] > a[i + 1]:
		l.append(a[i] - a[i + 1] + l[-1])
	else:
		l.append(l[-1])
	if a[i] < a[i + 1]:
		r.append(a[i + 1] - a[i] + r[-1])
	else:
		r.append(r[-1])
for i in range(0, m):
	(sj, tj) = map(int, input().split())
	if sj <= tj:
		print(l[tj - 1] - l[sj - 1])
	else:
		print(r[sj - 1] - r[tj - 1])


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
f = [0] * n
b = [0] * n
d = 0
for j in range(1, n):
	d = d + max(0, l[j - 1] - l[j])
	f[j] = d
l = l[::-1]
d = 0
for k in range(1, n):
	d = d + max(0, l[k - 1] - l[k])
	b[k] = d
b = b[::-1]
for i in range(m):
	(s, t) = map(int, input().split())
	if s < t:
		print(f[t - 1] - f[s - 1])
	else:
		print(b[t - 1] - b[s - 1])