题目链接： https://vjudge.net/problem/SPOJ-DRUIDEOI
题意：
题意
n个数形成一个环，定义1号的左边是n号，位置i的数值为hi。
输出每一个数左边和右边，第一个比他大的数的位置,如果不存在这样的位置，输出-1。
数据
测试样例数T, (1 <= T <= 20)。
(1 <= n <= 1e5，1 <= hi <= 1e9)。
输入
3
5
172 170 168 171 169
3
172 169 172
1
172
输出
-1 -1
1 4
2 4
1 1
4 1
-1 -1
1 3
-1 -1
-1 -1

解题方法：
因为数字是一个圈而不是一条线。所以第一步是把数组倍增（用来模拟圈）。好，现在问题变成了如何求前面和后面第一个比它大的。这件事情可以用单调栈做。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define uep(i, a, b) for(int i = a; i >= b; i--)
#define cls(a, b) memset(a, b, sizeof(a))
const int maxn = 300010;
int a[maxn], L[maxn], R[maxn], T, n;
int stk[maxn], top;
int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        cls(L, 0); cls(R, 0);
        top = 0;
        rep(i, 1, n) scanf("%d", &a[i]), a[i + n] = a[i];
        rep(i, 1, 2*n){
            if(!top) L[i] = -1, stk[++top] = i;
            else if(a[i] >= a[stk[top]]){
                while(top > 0 && a[i] >= a[stk[top]]) --top;
                if(top != 0) L[i] = stk[top];
                else L[i] = -1;
                stk[++top]  = i;
            }
            else L[i] = stk[top], stk[++top] = i;
        }
        top = 0;
        uep(i, 2*n, 1){
            if(!top) R[i] = -1, stk[++top] = i;
            else if(a[i] >= a[stk[top]]){
                while(top != 0 && a[i] >= a[stk[top]]) --top;
                if(top != 0) R[i] = stk[top];
                else R[i] = -1;
                stk[++top] = i;
            }
            else R[i] = stk[top], stk[++top] = i;
        }
        rep(i, n + 1, n*2){
            if(L[i] <= n) printf("%d ", L[i]);
            else printf("%d ", L[i] - n);
            if(R[i - n] <= n) printf("%d\n", R[i - n]);
            else printf("%d\n", R[i - n] - n);
        }
    }
    return 0;
}