0-indexed とする． 区間毎に値を振っておく． 偶数番目とき数番目の区間に対して，0 と 区間の長さを対応させる． この値に関して累積和をとればよい． 区間の端だけ中途半端になりうるので微調整．
\(l,r\)が与えられたときに，どの区間に\(l,r\)が入るのかは binary search で求まる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n;
cin >> n;
vll a(n); rep(i,n) { cin >> a[i]; }
vll s(n+1);
rep(i,n-1){
ll d = a[i+1] - a[i];
if(i%2){
s[i+1] = s[i] + d;
}else{
// get up
s[i+1] = s[i];
}
}
ll q; cin >> q;
rep(qi,q){
ll l, r; cin >> l >> r;
ll ans = 0;
auto itl = lower_bound(all(a), l);
auto itr = lower_bound(all(a), r);
ll jl = itl - a.begin();
ll jr = itr - a.begin();
if(jl % 2){
}else{
ans += (*itl) - l;
}
if(jr % 2){
}else {
ans -= (*itr) - r;
}
ans += s[jr] - s[jl];
cout << ans << endl;
}
return 0;
}
