g5-08214. 下一个更大元素 未做

给一排 $n$ 个数，对每个数都找它右边第一个比它大的数，找到就输出那个数，右边不存在比它大的数就输出 $-1$。

从右往左扫描，手里维护一个栈：栈里存的是「位置 $i$ 右边还活着的高度候选」。新来的数会淘汰掉栈顶所有不比它大的候选——它们既够不着自己，更够不着 $i$ 左边的数。淘汰完剩下的栈顶就是答案；这就是单调栈。

第一行一个整数 $n$（$1\le n\le 10^5$）。

第二行 $n$ 个整数 $a_i$（$-10^9\le a_i\le 10^9$）。

一行 $n$ 个整数：每个数右边第一个比它大的数（没有为 $-1$），用空格分隔。

输入：

3
1 5 3

输出：

5 -1 -1

1 右边第一个更大的是 5；5 和 3 右边都没有比它们大的数。

$1\le n\le 10^5$。对每个数往右扫一格找答案是 $O(n^2)$——一万个全相等的数就能把它卡死；单调栈一轮 $O(n)$。