返回小组 开始 2024-08-15 13:21:37

单调队列与单调栈

结束 2024-08-18 00:00:00
Contest is over.
当前 2024-09-19 10:01:02

E. 向右看齐(Look Up S)

描述

约翰的N(1≤N≤105)头奶牛站成一排,奶牛i的身高是Hi(1≤Hi≤10^6)。现在,每只奶牛都在向右看齐。对于奶牛i,如果奶牛j满足 i<j且Hi < Hj,我们可以说奶牛i可以仰望奶牛j。求出每只奶牛离她最近的仰望对象。

输入

第1行输入N,之后N行中每行输入一个身高Hi。

输出

共N行,按顺序每行输出一只奶牛的最近仰望对象,如果没有仰望对象,输出0。

样例

输入

6
3
2
6
1
1
2

输出

3
3
0
6
6
0

提示

【输入说明】

6头奶牛的身高分别为3,2,6,1,1,2。

【输出说明】

奶牛#1,#2仰望奶牛#3,奶牛#4,#5仰望奶牛#6,奶牛#3和#6没有仰望对象。

【数据规模】

对于20%的数据:1≤N≤10;

对于50%的数据:1≤N≤10^3;

对于100%的数据:1≤N≤10^5,1≤Hi≤10^6。


Submit

登录

注册
时间限制 1 秒
内存限制 128 MB
提交