如果你和我一样写了st表，交完题后发现这题cf1300分而后懊恼破防，那你一定遇到同道中人。总结一下，这道题之所以不用使用st表，而是直接使用前缀和，原因是除了最近城市之外的所有城市，不论如何选择跳越的方式，代价都是相同的，所以不用考虑当前最佳，因为无论怎么跳，都可以以最佳代价到达目的地。下面附上蒟蒻的st解法。

#include <bits/stdc++.h>
using namespace std;

int main (){

	int t = 1;
	cin >> t;
	

	for (int tt=0;tt<t;tt++){
		int n;
		cin >> n;
		vector<int> hold (n);
		for (int c=0;c<n;c++) scanf ("%d",&hold[c]);
		vector<vector<long long>> st1(18,vector<long long>(n));
		st1[0][0] = 1;
		for (int c=1;c<n-1;c++){
			if (hold[c+1]-hold[c] <= hold[c]-hold[c-1]){
				st1[0][c] = 1;
			}
			else st1[0][c] = hold[c+1] - hold[c];
		}
		for (int p=1;p<19;p++){
			for (int c=0;c+(1<<(p-1))<n;c++){
				st1[p][c] = st1[p-1][c] + st1[p-1][c+(1<<(p-1))];
			}
		}


		reverse(hold.begin(),hold.end());
		for (int c=0;c<n;c++) hold[c] = 1e9 - hold[c];
		vector<vector<long long>> st2(18,vector<long long>(n));
		st2[0][0] = 1;
		for (int c=1;c<n-1;c++){
			if (hold[c+1]-hold[c] <= hold[c]-hold[c-1]){
				st2[0][c] = 1;
			}
			else st2[0][c] = hold[c+1] - hold[c];
		}
		for (int p=1;p<19;p++){
			for (int c=0;c+(1<<(p-1))<n;c++){
				st2[p][c] = st2[p-1][c] + st2[p-1][c+(1<<(p-1))];
			}
		}


		int m;
		cin >> m;
		for (int q=0;q<m;q++){
			int a,b;
			scanf ("%d%d",&a,&b);
			a--,b--;
			if (a < b){
				int cha = b - a;
				int now = a;
				long long sum = 0;
				for (int c=17;c>=0;c--){
					if (1<<c <= cha){
						sum += st1[c][now];
						now += 1<<c;
						cha -= 1<<c;
					}
				}
				cout << sum << endl;
			}
			else{
				a = n-a-1;
				b = n-b-1;

				int cha = b - a;
				int now = a;
				long long sum = 0;
				for (int c=17;c>=0;c--){
					if (1<<c <= cha){
						sum += st2[c][now];
						now += 1<<c;
						cha -= 1<<c;
					}
				}
				cout << sum << endl;
			}
		}
	}
}