5C. Tourism.py

"""
Александр недавно увлекся горным туризмом. Ему уже надоело покорять отдельные горные
пики, и он собирается покорить самую настоящую горную цепь!
Напомним, что Александр живет в плоском мире. Горная цепь состоит из отрезков, соединяющих
точки на плоскости, каждая из которых находится строго правее предыдущей (x-координата
следующей точки больше, чем у предыдущей). Трассой на горной цепи называется её
часть между двумя фиксированными концами отрезков.
Участок, на котором при движении по трассе координата y (высота) всегда возрастает,
называется подъемом, величиной подъема называется разность высот между начальной
и конечной точками участка.
Туристическая компания предлагает на выбор несколько трасс на одной горной цепи.
Александр из-за финансовых трудностей может выбрать для поездки только одну из этих
трасс. Вы решили помочь ему с выбором. Александру важно для каждой трассы определить
суммарную высоту подъемов на ней. Обратите внимание, что трасса может идти как слева-направо,
так и справа-налево.

Формат ввода
В первой строке входного файла содержится единственное число N — количество точек
ломаной, задающей горную цепь (1 ≤ N ≤ 30 000). Далее в N строках содержатся описания
точек, каждое из которых состоит из двух целых чисел, xi и yi (1 ≤ xi, yi ≤ 30 000).
В следующей строке находится число M — количество трасс (1 ≤ M ≤ 30 000).
Далее в M строках содержатся описания трасс. Каждое описание представляет собой
два целых числа, si и fi, они обозначают номера вершин начала и конца трассы, соответственно
(1 ≤ si ≤ N, 1 ≤ fi ≤ N). Начало и конец трассы могут совпадать.
Гарантируется, что во входном файле задана именно горная цепь.

Формат вывода
Для каждой трассы выведите одно число — суммарную высоту подъемов на данной трассе.

Пример 1
Ввод
Вывод
7
2 1
4 5
7 4
8 2
9 6
11 3
15 3
1
2 6

4

Пример 2
Ввод
Вывод
6
1 1
3 2
5 6
7 2
10 4
11 1
3
5 6
1 4
4 2

0
5
4
"""


def fun(s, t):
    """
    >>> fun([1, 5, 4, 2, 6, 3, 3], [(2, 6)])
    [4]
    >>> fun([1, 2, 6, 2, 4, 1], [(5, 6), (1, 4), (4, 2)])
    [0, 5, 4]
    """

    s = [0] + s
    up = [0] * len(s)
    down = [0] * len(s)

    for i in range(1, len(s)):
        cur = s[i]
        prev = s[i - 1]
        if cur < prev:
            up[i] = up[i - 1]
            down[i] = down[i - 1] + prev - cur
        else:
            up[i] = up[i - 1] + cur - prev
            down[i] = down[i - 1]

    ans = []
    for start, end in t:
        if start < end:
            ans.append(up[end] - up[start])
        else:
            ans.append(down[start] - down[end])

    return ans


N = int(input())
s = [tuple(map(int, input().split()))[1] for _ in range(N)]
M = int(input())
t = [tuple(map(int, input().split())) for _ in range(M)]
print(*fun(s, t), sep="\n")

# print(f">>> fun({s}, {t})")
# print(f"{fun(s, t)}")


if __name__ == "__main__":
    import doctest

    doctest.testmod()