C. Closest Cities

有n个城市位于数字线上，第i个城市位于点ai。城市的坐标是按升序排列的，a1 < a2 < a3 < …… < an。
两个城市 x 和 y 之间的距离等于|ax−ay|。

对于每个城市 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，支付|ax-ay|枚硬币；
前往离 x 最近的城市，支付1枚硬币。

您将收到 m 个查询。在每次查询中，您将获得两个城市，您必须计算从一个城市到另一个城市所需花费的最低硬币数量。

输入
第一行包含一个整数 t（1 ≤ t ≤ 1e4）——测试用例的数量。
每个测试用例的格式如下：
第一行包含一个整数 n（2 ≤ n ≤ 1e5）；
第二行包含 n 个整数 a1，a2，…，an（0 ≤a1＜a2＜…＜an≤ 1e9）；
第三行包含一个整数 m（1 ≤ m ≤ 1e5）；
接下来 m 行，其中第i个包含两个整数 xi 和 yi(1≤xi，yi≤n；xi≠yi)，表示在第i个查询中，您必须计算从 xi 市到 yi 市所需花费的最小硬币数。
对输入的附加约束：在每个测试用例中，对于每个城市，唯一地确定最近的城市；所有测试用例的 n 之和不超过1e5；所有测试用例的 m 之和不超过1e5。

输出
对于每个查询，打印一个整数——您必须花费的最小硬币数量。

Input
1
5
0 8 12 15 20
5
1 4
1 5
3 4
3 2
5 1

Output
3
8
1
4
14

注意：
让我们考虑示例中的前两个查询：
在第一个查询中，您最初位于城市1。您可以支付1枚硬币前往最近的城市（即城市2）。然后你再次前往最近的城市（即城市3），支付1枚硬币。然后你再次前往最近的城市（即城市4），支付1枚硬币。你总共花了3个硬币从城市1到城市4；
在第二个查询中，您可以使用相同的方式从城市1到城市4，然后花费5个硬币从城市4到城市5。

解析：

正常维护前缀和，后缀和就行。不过要记住初始化 s[1]=0,p[n]=0 ！！！！

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=2e6+10;
int n,m;
int a[N],s[N],p[N];
void solve()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    s[1]=p[n]=0;
    s[2]=1;
    for (int i=3;i<=n;i++)
    {
        int l=abs(a[i-1]-a[i-2]),r=abs(a[i]-a[i-1]);
        if (r<l) s[i]=s[i-1]+1;
        else s[i]=s[i-1]+r;
    }
    p[n-1]=1;
    for (int i=n-2;i>0;i--)
    {
        int l=abs(a[i+1]-a[i]),r=abs(a[i+2]-a[i+1]);
        if (l<r) p[i]=p[i+1]+1;
        else p[i]=p[i+1]+l;
    }
    for (int i=1;i<=n;i++) cout<<s[i]<<" ";
    cout<<endl;
    for (int i=1;i<=n;i++) cout<<p[i]<<" ";
    cout<<endl;
    cin>>m;
    while (m--)
    {
        int x,y;
        cin>>x>>y;
        if (x<y) cout<<s[y]-s[x]<<endl;
        else cout<<p[y]-p[x]<<endl;
    }
}
signed main()
{
    ios;
    int T=1;
    cin>>T;
    while (T--) solve(); 
    return 0;
}