题目链接：点击打开链接

题意：

给定n座山

以下n个数字表示n座山的高度

若这座山u合法，则要满足：

1、若u的左边存在比u高的山，设v是u左边距离u近期的且严格比u高的山，在[v,u]之间至少有一座山x，使得x和u的高度差>=15000

2、右边也同理。

同一时候满足1、2的情况则算合法。

问：

输出全部合法的山。

思路：

求距离某个点近期的山就是维护一个单调栈，然后给山的高度求一个RMQ。

写写写。。。

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

template <class T>

inline bool rd(T &ret) {

    char c; int sgn;

    if(c=getchar(),c==EOF) return 0;

    while(c!='-'&&(c<'0'||c>'9')) c=getchar();

    sgn=(c=='-')?-1:1;

    ret=(c=='-')?0:(c-'0');

    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');

    ret*=sgn;

    return 1;

}

template <class T>

inline void pt(T x) {

    if (x <0) {

        putchar('-');

        x = -x;

    }

    if(x>9) pt(x/10);

    putchar(x%10+'0');

}

using namespace std;

typedef long long ll;

const int N = 100050;

int d[N*2][20];

void RMQ_init(int *A, int n) {

	for (int i = 1; i <= n; ++i)

		d[i][0] = A[i];

	for (int j = 1; (1 << j) <= n; ++j)

		for (int i = 1; i + j - 1 <= n; ++i) {

			d[i][j] = min(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);

		}

}

int RMQ(int L, int R) {

	int k = 0;

	while ((1 << (k + 1)) <= R - L + 1)

		++k;

	return min(d[L][k], d[R - (1 << k) + 1][k]);

}

int n, h[N], Stack[N], top;

int lh[N], rh[N];

void work(){

    for(int i = 1; i <= n; i++)rd(h[i]);

    top = 0;

    for(int i = 1; i <= n; i++) {

        while(top && h[ Stack[top-1] ] <= h[i])top--;

        if(top) lh[i] = Stack[top-1];

        else lh[i] = 0;

        Stack[top++] = i;

    }

    top = 0;

    for(int i = n; i; i--){

        while(top && h[ Stack[top-1] ]<= h[i])top--;

        if(top) rh[i] = Stack[top-1];

        else rh[i] = 0;

        Stack[top++] = i;

    }

}

const int hehe = 150000;

vector<int>ans;

int main(){

	while(cin>>n){

        work();

        RMQ_init(h, n);

        ans.clear();

        for(int i =1; i <= n; i++){

            if(lh[i] == 0 && rh[i] == 0) ans.push_back(i);

            else if(lh[i] == 0){

                int v = RMQ(i, rh[i]);

                if(h[i] - v >= hehe)

                    ans.push_back(i);

            }

            else if(rh[i] == 0){

                int v = RMQ(lh[i], i);

                if(h[i] - v >= hehe)

                     ans.push_back(i);

            }

            else {

                int u = RMQ(lh[i], i), v = RMQ(i, rh[i]);

                int maxx = max(u, v);

                if(h[i] - maxx >= hehe)

                     ans.push_back(i);

            }

        }

        for(int i = 0; i < ans.size(); i++){

            pt(ans[i]);

            if(i==ans.size()-1)puts("");

            else putchar(' ');

        }

    }

	return 0;

}