92. Туризм

Горная цепь состоит из отрезков, соединяющих точки на плоскости, каждая из которых находится правее предыдущей (координата $x$ строго возрастает).

Трассой на горной цепи называется маршрут по отрезкам цепи из одной точки в другую. Трассы ориентированы — то есть маршрут может быть как слева направо, так и справа налево.

Подъёмом на трассе называется такой отрезок, на котором высота (координата $y$) возрастает, а высотой подъёма — разность высот между начальной и конечной точками отрезка.

Вам даны несколько трасс на одной горной цепи. Помогите для каждой трассы определить суммарную высоту подъёмов.

В первой строке содержится число $N$ ($1 \le N \le 30\,000$) — количество точек в цепи, задающей горную цепь. Далее в $N$ строках содержатся координаты точек — два целых числа $x_i$ и $y_i$ ​($1 \le x_i, y_i \le 30\,000$, $x_i \le x_{i+1}$).

В следующей строке находится число $M$ — количество трасс ($1 \le M \le 30\,000$).

Далее в $M$ строках содержатся описания трасс. Каждое описание представляет собой два целых числа, $s_i$ и $f_i$ ($1 \le s_i, f_i, \le N$) — номера точек начала и конца трассы. Начало и конец трассы могут совпадать. Точки нумеруются с единицы.

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