110004 - [USACO09MAR] Look Up S

通过次数

3

提交次数

3

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

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

输入

第 1 行输入 N,之后每行输入一个身高 H_i​。

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

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

输出

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 没有仰望对象。