4211: 云顶之弈的思考
内存限制：128 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：85
通过：23
题目描述
pl在玩云顶之弈时，他的N(1≤N≤10^5)个英雄站成一排，于是它思考英雄i的身高是Hi(1≤Hi≤1,000,000)．现在，每个英雄都在向右看齐．对于i英雄，如果英雄j满足i<j且Hi<Hj，我们可以说英雄i可以仰望英雄j． 求出每个英雄离她最近的仰望对象．
输入格式
第 1 行输入 N，之后每行输入一个身高 H_i。
输出格式
共 N 行，按顺序每行输出一个英雄的最近仰望对象，如果没有仰望对象，输出 0。
输入样例 复制
6
3
2
6
1
1
2 输出样例 复制
3
3
0
6
6
0 数据范围与提示
简单的二层循环会超时。最近学了KMP算法。有一个跳跃思维能减少运行时间
【输入说明】6 个英雄的身高分别为 3, 2, 6, 1, 1, 2.
【输出说明】英雄#1,#2 仰望英雄#3，英雄#4,#5 仰望英雄#6，英雄#3 和#6 没有仰望对象。
【数据规模】
对于 20%的数据： 1≤N≤10；
对于 50%的数据： 1≤N≤1,000；
对于 100%的数据：1≤N≤100,000；1≤H_i≤1,000,000；
【输入说明】6 个英雄的身高分别为 3, 2, 6, 1, 1, 2.
【输出说明】英雄#1,#2 仰望英雄#3，英雄#4,#5 仰望英雄#6，英雄#3 和#6 没有仰望对象。
【数据规模】
对于 20%的数据： 1≤N≤10；
对于 50%的数据： 1≤N≤1,000；
对于 100%的数据：1≤N≤100,000；1≤H_i≤1,000,000；