题意：1e5个数围成一个环。现在要输出每个数左右第一个大于它的数的下标。若没有，则输出-1.
题解：单调栈板题。只是要把数据压入栈压两遍来模仿环。
具体分析：考虑一个递减的数列。要找左边最大的数，我们从左到右对于每一个数，只要往回枚举一步就能找到，时间复杂度为O（n）；
考虑一个递增的数列。同样用暴力枚举，每次都要找到头（尾），复杂度为O(n*n); 如何优化？
我们发现在递增数列的例子中如果a[N]一直遍历到头才停止，那么只要a[N+1]>a[N],就可以直接跳过之前的n-1次遍历。
那如何记录“一直遍历到某点才停止”呢？
一种方法是写一个数组，记录可以走到最远的地方有点记忆递归的意思。
另一种就是把遍历过的数全删光，这就是单调栈的思想。
#define _CRT_SECURE_NO_WARNINGS
#include<cstring>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<string>
#include<stack>
#include<ctime>
#include<list>
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<sstream>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
#define N 1111
#define eps 1e-6
#define pi acos(-1.0)
#define e exp(1.0)
//std::ios::sync_with_stdio(false);
using namespace std; const int maxn = 1e5 + ;
const int mod = 1e9 + ;
typedef long long ll;
typedef unsigned long long ull; stack<int>s;
deque<int>l, r;
int h[maxn];
#define ONLINE_JUDGE
int main() { #ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
long _begin_time = clock();
#endif
int t; cin >> t; while (t--) {
int n;
while (!s.empty())s.pop();
l.clear(), r.clear(); cin >> n;
int mx = , mxi = ;
for (int i = ; i <= n; i++) {
scanf("%d", &h[i]); while (!s.empty() && h[s.top()] <= h[i])s.pop(); s.push(i);//存 个下降子序列 末位是最高的那个
}
for (int i = ; i <= n; i++) {
while (!s.empty() && h[s.top()] <= h[i])s.pop();
if (!s.empty())l.push_back(s.top());
else l.push_back(-);
s.push(i);
}
while (!s.empty())s.pop();
for (int i = n; i > ; i--) {
while (!s.empty() && h[s.top()] <= h[i])s.pop(); s.push(i);
}
for (int i = n; i > ; i--) {
while (!s.empty() && h[s.top()] <= h[i])s.pop();
if (!s.empty())r.push_front(s.top());
else r.push_front(-);
s.push(i);
}
int sz = l.size();
for (int i = ; i < sz; i++) {
printf("%d %d\n", l[i], r[i]);
}
}
#ifndef ONLINE_JUDGE
long _end_time = clock();
printf("time = %ld ms.", _end_time - _begin_time);
#endif
return ;
}