人生第一道单调队列！

---

我曾经给自己提出过这么一个问题，但是解决不了。没想到单调队列搞一搞就好了。

这道题就是要你找出一个数中右边的最靠近的一个比它大的数字，输出它的下标。

\(O(n^2)\)的方法就是暴力，57分。我们看看如何使用单调队列解决。

我们可以维护一个下降的序列，在单调队列中。

如果一个新元素要加入，被插队而删除掉的那些数的答案其实就是它！

所以暴力搞一搞就可以了。

因为左端点不存在限制，其实就是一个单调栈了吧。。。

如果左端点存在限制，我们就看下一道题：

代码：

#include
    
     #include
     
      const int maxn = 100005;std::deque
      
        q;int a[maxn], ans[maxn], n;int main(){    scanf("%d", &n);    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);    for(int i = 1; i <= n; i++)    {        while(!q.empty() && a[i] > a[q.back()])        {            ans[q.back()] = i;            q.pop_back();        }        q.push_back(i);    }    for(int i = 1; i <= n; i++) printf("%d\n", ans[i]);    return 0;}