На числовой прямой расположены \(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\) запросов. В каждом запросе вам будут даны два города, и вам нужно вычислить минимальное количество монет, которое придется потратить, чтобы переместиться из одного города в другой.