约翰的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。
时间限制 | 1 秒 |
内存限制 | 128 MB |