#include <bits/stdc++.h>
using namespace std;
 
int main(){
 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t;cin>>t;
while(t--){
 int n;cin>>n;
vector<int> a(n+2);
 for(int i=1;i<=n;i++)cin>>a[i];
 
 vector<int> pfxL(n+2),pfxR(n+2);
 for(int i=2;i<=n;i++)
 pfxL[i]=pfxL[i-1]+(a[i]-a[i-1]>a[i+1]-a[i]?1:a[i+1]-a[i]);
 for(int i=n-1;i>=1;i--)
 pfxR[i]=pfxR[i+1]+(a[i]-a[i+1]<a[i+1]-a[i]?1:a[i]-a[i-1]);
 
 int q;cin>>q;
while(q--){
 int a,b;cin>>a>>b;
 if(a<b)cout<<pfxL[b]-pfxL[a-1];
 else cout<<pfxR[a]-pfxR[b+1];
 cout<<'\n';
}
 
 }
return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpewogaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7Y2luLnRpZSgwKTtjb3V0LnRpZSgwKTsKaW50IHQ7Y2luPj50Owp3aGlsZSh0LS0pewogaW50IG47Y2luPj5uOwp2ZWN0b3I8aW50PiBhKG4rMik7CiBmb3IoaW50IGk9MTtpPD1uO2krKyljaW4+PmFbaV07CiAKIHZlY3RvcjxpbnQ+IHBmeEwobisyKSxwZnhSKG4rMik7CiBmb3IoaW50IGk9MjtpPD1uO2krKykKIHBmeExbaV09cGZ4TFtpLTFdKyhhW2ldLWFbaS0xXT5hW2krMV0tYVtpXT8xOmFbaSsxXS1hW2ldKTsKIGZvcihpbnQgaT1uLTE7aT49MTtpLS0pCiBwZnhSW2ldPXBmeFJbaSsxXSsoYVtpXS1hW2krMV08YVtpKzFdLWFbaV0/MTphW2ldLWFbaS0xXSk7CiAKIGludCBxO2Npbj4+cTsKd2hpbGUocS0tKXsKIGludCBhLGI7Y2luPj5hPj5iOwogaWYoYTxiKWNvdXQ8PHBmeExbYl0tcGZ4TFthLTFdOwogZWxzZSBjb3V0PDxwZnhSW2FdLXBmeFJbYisxXTsKIGNvdXQ8PCdcbic7Cn0KIAkKIH0KcmV0dXJuIDA7Cn0=

MQo1CjAgOCAxMiAxNSAyMAo1CjEgNAoxIDUKMyA0CjMgMgo1IDE=

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