Toph - maximum-distance / Segment Tree

///Problem Link - "https://toph.co/p/maximum-distance"

/***
 created: 2022-04-14-21.52.40
***/
a
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
#define nl '\n'

ll a[100005],s[100005],p[100005];
pair<ll,ll> tree[400005];
pair<ll,ll> tree1[400005];
pair<ll,ll> tree2[400005];
pair<ll,ll> tree3[400005];

void treeconstruct(ll node,ll b,ll e)
{
    if(b==e)
    {
        tree[node]={p[b],b};
        tree1[node]={p[b],b};
        return;
    }

    ll left = node*2;
    ll right = node*2 + 1ll;

    ll mid=(b+e)/2;

    treeconstruct(left,b,mid);
    treeconstruct(right,mid+1,e);

    tree[node]=min(tree[left],tree[right]);

    tree1[node]=max(tree1[left],tree1[right]);

}


void treeconstruct1(ll node,ll b,ll e)
{
    if(b==e)
    {
        tree2[node]={s[b],b};
        tree3[node]={s[b],b};
        return;
    }

    ll left = node*2;
    ll right = node*2 + 1ll;

    ll mid=(b+e)/2;

    treeconstruct1(left,b,mid);
    treeconstruct1(right,mid+1,e);

    tree2[node]=min(tree2[left],tree2[right]);

    tree3[node]=max(tree3[left],tree3[right]);

}


pair<ll,ll> queries(ll node,ll b,ll e,ll i,ll j)
{
    if(i>e || j<b) return {1e17,0};

    if(b>=i && e<=j) return tree[node];

    ll left = node*2;
    ll right = node*2 + 1ll;

    ll mid=(b+e)/2;

    return min(queries(left,b,mid,i,j),queries(right,mid+1,e,i,j));
}


pair<ll,ll> queries1(ll node,ll b,ll e,ll i,ll j)
{
    if(i>e || j<b) return {-1e17,0};

    if(b>=i && e<=j) return tree1[node];

    ll left = node*2;
    ll right = node*2 + 1ll;

    ll mid=(b+e)/2;

    return max(queries1(left,b,mid,i,j),queries1(right,mid+1,e,i,j));
}


pair<ll,ll> queries2(ll node,ll b,ll e,ll i,ll j)
{
    if(i>e || j<b) return {1e17,0};

    if(b>=i && e<=j) return tree2[node];

    ll left = node*2;
    ll right = node*2 + 1ll;

    ll mid=(b+e)/2;

    return min(queries2(left,b,mid,i,j),queries2(right,mid+1,e,i,j));
}


pair<ll,ll> queries3(ll node,ll b,ll e,ll i,ll j)
{
    if(i>e || j<b) return {-1e17,0};

    if(b>=i && e<=j) return tree3[node];

    ll left = node*2;
    ll right = node*2 + 1ll;

    ll mid=(b+e)/2;

    return max(queries3(left,b,mid,i,j),queries3(right,mid+1,e,i,j));
}



int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    test
    {
        ll n,m,i,j,k,l,q;

        cin>>n;

        for(i=1;i<=n;i++)
        {
            cin>>a[i];
        }

        p[0]=0;
        s[n+1]=0;

        for(i=1;i<=n;i++) p[i]=p[i-1]+a[i];
        for(i=n;i>=0;i--) s[i]=s[i+1]+a[i];

        treeconstruct(1,1,n);
        treeconstruct1(1,1,n);

        cin>>q;

        while(q--)
        {
            cin>>j>>k;

            auto x=queries(1,1,n,j,k);  // min prefix sum

            auto y=queries1(1,1,n,j,k); // max prefix sum

            auto z=queries2(1,1,n,j,k); // min suffix sum

            auto w=queries3(1,1,n,j,k); // min suffix sum

            ll ans1=abs(y.first - p[j-1] - z.first + s[k+1]);

            ll ans2=abs(x.first - p[j-1] - w.first + s[k+1]);

            if(ans1<ans2)
            {
                cout<<x.second<<" "<<w.second<<nl;
            }
            else
            {
                cout<<y.second<<" "<<z.second<<nl;
            }
        }
    }

    return 0;
}