C. Ближайшие города
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На числовой прямой расположены $$$n$$$ городов, $$$i$$$-й город находится в точке $$$a_i$$$. Координаты городов заданы в порядке возрастания, т. е. $$$a_1 < a_2 < \dots < a_n$$$.

Расстояние между двумя городами $$$x$$$ и $$$y$$$ равно $$$|a_x - a_y|$$$.

Для каждого города $$$i$$$ определим ближайший город $$$j$$$ как город, для которого расстояние между $$$i$$$ и $$$j$$$ не больше, чем расстояние между $$$i$$$ и каждым другим городом $$$k$$$. Например, если города расположены в точках $$$[0, 8, 12, 15, 20]$$$, то:

  • ближайший город к городу $$$1$$$ — город $$$2$$$;
  • ближайший город к городу $$$2$$$ — город $$$3$$$;
  • ближайший город к городу $$$3$$$ — город $$$4$$$;
  • ближайший город к городу $$$4$$$ — город $$$3$$$;
  • ближайший город к городу $$$5$$$ — город $$$4$$$.

Города расположены таким образом, что для каждого города ближайший город уникален. Например, невозможно, чтобы города находились в точках $$$[1, 2, 3]$$$, так как это означало бы, что у города $$$2$$$ два ближайших города ($$$1$$$ и $$$3$$$), оба на расстоянии $$$1$$$.

Вы можете перемещаться между городами. Предположим, что вы находитесь в городе $$$x$$$. Тогда вы можете выполнить одно из следующих действий:

  • переместиться в любой другой город $$$y$$$, заплатив $$$|a_x - a_y|$$$ монет;
  • переместиться в ближайший к $$$x$$$ город, заплатив $$$1$$$ монету.

Вам даны $$$m$$$ запросов. В каждом запросе вам будут даны два города, и вам нужно вычислить минимальное количество монет, которое придется потратить, чтобы переместиться из одного города в другой.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных задается в следующем формате:

  • первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 10^5$$$);
  • вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_1 < a_2 < \dots < a_n \le 10^9$$$);
  • третья строка содержит одно целое число $$$m$$$ ($$$1 \le m \le 10^5$$$);
  • затем следуют $$$m$$$ строк; $$$i$$$-я из них содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$), что означает, что в $$$i$$$-м запросе вам нужно вычислить минимальное количество монет, которое придется потратить, чтобы переместиться из города $$$x_i$$$ в город $$$y_i$$$.

Дополнительные ограничения на входные данные:

  • в каждом наборе входных данных для каждого города ближайший город определяется однозначно;
  • сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^5$$$;
  • сумма $$$m$$$ по всем наборам входных данных не превышает $$$10^5$$$.
Выходные данные

Для каждого запроса выведите одно целое число — минимальное количество монет, которое придется потратить.

Пример
Входные данные
1
5
0 8 12 15 20
5
1 4
1 5
3 4
3 2
5 1
Выходные данные
3
8
1
4
14
Примечание

Рассмотрим первые два запроса в примере из условия:

  • в первом запросе вы изначально находитесь в городе $$$1$$$. Вы можете переместиться в ближайший город (который является городом $$$2$$$), заплатив $$$1$$$ монету. Затем вы снова перемещаетесь в ближайший город (который является городом $$$3$$$), заплатив $$$1$$$ монету. Затем вы снова перемещаетесь в ближайший город (который является городом $$$4$$$), заплатив $$$1$$$ монету. Всего вы потратите $$$3$$$ монеты, чтобы попасть из города $$$1$$$ в город $$$4$$$;
  • во втором запросе вы можете использовать тот же способ, чтобы попасть из города $$$1$$$ в город $$$4$$$, а затем потратить $$$5$$$ монет, чтобы переместиться из города $$$4$$$ в город $$$5$$$.