Задача №3591. Туризм
Александр недавно увлекся горным туризмом. Ему уже надоело покорять отдельные горные пики, и он собирается покорить самую настоящую горную цепь!
Напомним, что Александр живет в плоском мире. Горная цепь состоит из отрезков, соединяющих точки на плоскости, каждая из которых находится строго правее предыдущей (x-координата следующей точки больше, чем у предыдущей). Трассой на горной цепи называется её часть между двумя фиксированными концами отрезков.
Участок, на котором при движении по трассе координата y (высота) всегда возрастает, называется подъемом, величиной подъема называется разность высот между начальной и конечной точками участка. Ниже изображена горная цепь из 7 точек, на ней задана трасса, которая состоит из четырех участков (трасса выделена жирным). Если проходить трассу слева направо, то один из участков является подъемом.
Туристическая компания предлагает на выбор несколько трасс на одной горной цепи. Александр из-за финансовых трудностей может выбрать для поездки только одну из этих трасс. Вы решили помочь ему с выбором. Александру важно для каждой трассы определить суммарную высоту подъемов на ней.
В первой строке входного файла содержится единственное число 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). Начало и конец трассы могут совпадать.
Гарантируется, что во входном файле задана именно горная цепь.
Для каждой трассы выведите одно число — суммарную высоту подъемов на данной трассе.
7 2 1 4 5 7 4 8 2 9 6 11 3 15 3 1 2 6
4
6 1 1 3 2 5 6 7 2 10 4 11 1 3 5 6 1 4 4 2
0 5 4