#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
void solve() {
    int n; cin >> n;
    vector<int>a(n+1);

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

    ll ans = 0;

    vector<int>stk;
    vector<int>anss(n+1);
    for(int i = 1 ; i <= n ; i++){
        while(!stk.empty() && a[stk.back()] < a[i]) stk.pop_back();
        
        if(!stk.empty()) ans += i-stk.back()-1;
        else ans += i-1;
        cout<<ans<<" "<<a[i]<<endl;
        stk.push_back(i);
    }
    vector<int>stk2;
    for(int i = n ; i >= 1 ; i--){
        while(!stk2.empty() && a[stk2.back()] < a[i]) stk2.pop_back();
        if(!stk2.empty() && a[i]!=a[stk2.back()]) ans += stk2.back()-i-1;
        else if(stk2.empty())ans += n-i;
        cout<<ans<<" "<<a[i]<<endl;
        stk2.push_back(i);
    }
    cout<<ans<<endl;
}

int main()
{
    int t; cin >> t;
    while(t--) solve();
    return 0;
}