110004 - [USACO09MAR] Look Up S

通过次数

3

提交次数

3

时间限制 : 1 秒
内存限制 : 128 MB

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

输入

第 1 行输入 NN,之后每行输入一个身高 HiH_i​。

对于 50% 的数据:1N1031 \le N \le 10^3

对于 100% 的数据:1N105,1Hi1061 \le N \le 10^5,1 \le H_i ​\le 10^6

输出

NN行,按顺序每行输出一只奶牛的最近仰望对象,如果没有仰望对象,输出 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 没有仰望对象。