#911. [USACO2009MAR] Look Up S

[USACO2009MAR] Look Up S

题目描述

约翰的 N(1≤N≤105)N(1\le N\le10^5) 头奶牛从左到右站成一排,奶牛 ii 的身高是 Hi(1≤Hi≤106)H_i(1\le H_i\le10^6)。现在,每只奶牛都在向右看齐。对于奶牛 ii,如果奶牛 jj 满足 i<ji < j 且 Hi<HjH_i < H_j,我们可以说奶牛 ii 可以仰望奶牛 jj。 求出每只奶牛最近的仰望对象。

输入格式

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

输出格式

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

样例输入

6 
3 
2 
6 
1 
1 
2

样例输出

3 
3 
0 
6 
6 
0

样例解释

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

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

数据规模

对于 20%20\% 的数据:1≤N≤101\le N\le10;

对于 50%50\% 的数据:1≤N≤1031\le N\le10^3;

对于 100%100\% 的数据:1≤N≤105,1≤Hi≤1061\le N\le10^5,1\le H_i\le10^6。