思路：求每个人的左使者就是从左到右把每个人加入到单调队列中去，加入时最后一个出队的就是那个最大的小于这个数的数
求右信使同理
由于本题的单调队列队头不需要出队，所以其实是一个单调栈
/*
每个人只要找到左（右）边的比它小的最大的数即可，用单调队列模拟即可
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define maxn 50005
#define ll long long
using namespace std; int a[maxn],ans[maxn][],n; int main(){
int t;
scanf("%d",&t);
for(int tt=;tt<=t;tt++){
printf("Case %d:\n",tt);
memset(ans,,sizeof ans);
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
int last,l=,r=,q[maxn];
q[]=;
for(int i=;i<=n;i++){
last=;
while(l<r && a[i]>a[q[r-]])
r--,last=q[r];
q[r++]=i;ans[i][]=last?last:;
} q[]=;l=,r=;
for(int i=n;i>=;i--){
last=;
while(l<r && a[i]>a[q[r-]])
r--,last=q[r];
q[r++]=i;ans[i][]=last?last:;
}
for(int i=;i<=n;i++) printf("%d %d\n",ans[i][],ans[i][]);
}
return ;
}