Lipshitz Sequence
A function  is called Lipschitz continuous if there is a real constant K such that the inequality |f(x) - f(y)| ≤ K·|x - y| holds for all . We'll deal with a more... discrete version of this term.For an array , we define it's Lipschitz constant  as follows:  if n < 2,   if n ≥ 2,  over all 1 ≤ i < j ≤ n In other words,  is the smallest non-negative integer such that |h[i] - h[j]| ≤ L·|i - j| holds for all 1 ≤ i, j ≤ n.You are given an array  of size n and q queries of the form [l, r]. For each query, consider the subarray ; determine the sum of Lipschitz constants of all subarrays of .
In the first query of the first sample, the Lipschitz constants of subarrays of  with length at least 2 are:       The answer to the query is their sum.
The first line of the input contains two space-separated integers n and q (2 ≤ n ≤ 100 000 and 1 ≤ q ≤ 100) — the number of elements in array  and the number of queries respectively.The second line contains n space-separated integers  ().The following q lines describe queries. The i-th of those lines contains two space-separated integers li and ri (1 ≤ li < ri ≤ n).
Print the answers to all queries in the order in which they are given in the input. For the i-th query, print one line containing a single integer — the sum of Lipschitz constants of all subarrays of .
import sys

class FastIO:

    def __init__(self):
        return

    @staticmethod
    def read_str():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def read_int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def read_float():
        return float(sys.stdin.readline().rstrip())

    @staticmethod
    def read_ints():
        return map(int, sys.stdin.readline().rstrip().split())

    @staticmethod
    def read_floats():
        return map(float, sys.stdin.readline().rstrip().split())

    @staticmethod
    def read_ints_minus_one():
        return map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split())

    @staticmethod
    def read_list_ints():
        return list(map(int, sys.stdin.readline().rstrip().split()))

    @staticmethod
    def read_list_floats():
        return list(map(float, sys.stdin.readline().rstrip().split()))

    @staticmethod
    def read_list_ints_minus_one():
        return list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))

    @staticmethod
    def read_list_strs():
        return sys.stdin.readline().rstrip().split()

    @staticmethod
    def read_list_str():
        return list(sys.stdin.readline().rstrip())

    @staticmethod
    def st(x):
        return print(x)

    @staticmethod
    def lst(x):
        return print(*x)

    @staticmethod
    def round_5(f):
        res = int(f)
        if f - res >= 0.5:
            res += 1
        return res

    @staticmethod
    def max(a, b):
        return a if a > b else b

    @staticmethod
    def min(a, b):
        return a if a < b else b

    @staticmethod
    def accumulate(nums):
        n = len(nums)
        pre = [0] * (n + 1)
        for i in range(n):
            pre[i + 1] = pre[i] + nums[i]
        return pre

class Solution:

    def __init__(self):
        return

    @staticmethod
    def main(ac=FastIO()):
        (n, q) = ac.read_ints()
        nums = ac.read_list_ints()
        diff = [abs(nums[i + 1] - nums[i]) for i in range(n - 1)]
        post = [n - 2] * (n - 1)
        pre = [0] * (n - 1)
        stack = []
        for i in range(n - 1):
            v = diff[i]
            while stack and stack[-1][1] < v:
                post[stack.pop()[0]] = i - 1
            if stack:
                pre[i] = stack[-1][0] + 1
            stack.append([i, v])
        for _ in range(q):
            (l, r) = ac.read_ints_minus_one()
            ans = 0
            for i in range(l, r):
                ans += diff[i] * (i - ac.max(l, pre[i]) + 1) * (ac.min(post[i], r - 1) - i + 1)
            ac.st(ans)
        return
Solution().main()
from io import BytesIO, IOBase
import sys
import os
import bisect
import math
import random
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
from itertools import accumulate, combinations, permutations
from operator import add, iand, ior, itemgetter, mul, xor
from string import ascii_lowercase, ascii_uppercase
from typing import *

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
BUFSIZE = 4096

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
inf = float('inf')
(n, q) = MII()
nums = LII()
diff = [abs(y - x) for (x, y) in zip(nums, nums[1:])]
left_smaller = [None] * (n - 1)
stack = [(-1, inf)]
for i in range(n - 1):
    v = diff[i]
    while stack[-1][1] <= v:
        stack.pop()
    left_smaller[i] = stack[-1][0]
    stack.append((i, v))
right_smaller = [None] * (n - 1)
stack = [(n, inf)]
for i in range(n - 2, -1, -1):
    v = diff[i]
    while stack[-1][1] < v:
        stack.pop()
    right_smaller[i] = stack[-1][0]
    stack.append((i, v))
for _ in range(q):
    (l, r) = GMI()
    ans = 0
    for i in range(l, r):
        ans += diff[i] * (i - max(l - 1, left_smaller[i])) * (min(r, right_smaller[i]) - i)
    print(ans)
import sys

class FastIO:

    def __init__(self):
        return

    @staticmethod
    def read_str():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def read_int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def read_float():
        return float(sys.stdin.readline().rstrip())

    @staticmethod
    def read_ints():
        return map(int, sys.stdin.readline().rstrip().split())

    @staticmethod
    def read_floats():
        return map(float, sys.stdin.readline().rstrip().split())

    @staticmethod
    def read_ints_minus_one():
        return map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split())

    @staticmethod
    def read_list_ints():
        return list(map(int, sys.stdin.readline().rstrip().split()))

    @staticmethod
    def read_list_floats():
        return list(map(float, sys.stdin.readline().rstrip().split()))

    @staticmethod
    def read_list_ints_minus_one():
        return list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))

    @staticmethod
    def read_list_strs():
        return sys.stdin.readline().rstrip().split()

    @staticmethod
    def read_list_str():
        return list(sys.stdin.readline().rstrip())

    @staticmethod
    def st(x):
        return print(x)

    @staticmethod
    def lst(x):
        return print(*x)

    @staticmethod
    def round_5(f):
        res = int(f)
        if f - res >= 0.5:
            res += 1
        return res

    @staticmethod
    def max(a, b):
        return a if a > b else b

    @staticmethod
    def min(a, b):
        return a if a < b else b

    @staticmethod
    def accumulate(nums):
        n = len(nums)
        pre = [0] * (n + 1)
        for i in range(n):
            pre[i + 1] = pre[i] + nums[i]
        return pre

class Solution:

    def __init__(self):
        return

    @staticmethod
    def main(ac=FastIO()):
        (n, q) = ac.read_ints()
        nums = ac.read_list_ints()
        diff = [abs(nums[i + 1] - nums[i]) for i in range(n - 1)]
        post = [n - 2] * (n - 1)
        pre = [0] * (n - 1)
        stack = []
        for i in range(n - 1):
            while stack and diff[stack[-1]] < diff[i]:
                post[stack.pop()] = i - 1
            if stack:
                pre[i] = stack[-1] + 1
            stack.append(i)
        for _ in range(q):
            (l, r) = ac.read_ints_minus_one()
            ans = 0
            for i in range(l, r):
                ans += diff[i] * (i - ac.max(l, pre[i]) + 1) * (ac.min(post[i], r - 1) - i + 1)
            ac.st(ans)
        return
Solution().main()