LG#P2947. 向右看齐

向右看齐

P2947 [USACO09MAR] Look Up S

题目描述

\hspace{15pt}约翰的奶牛们站成一排,从左往右依次编号为 1,2,…,n1, 2, \dots, n,第 ii 头奶牛的身高为 hih_i。

\hspace{15pt}现在每头奶牛都在向右看。对于奶牛 ii 和奶牛 jj,若 i<ji < j 且 hi<hjh_i < h_j,则称奶牛 ii 可以仰望奶牛 jj。

\hspace{15pt}请对每头奶牛求出它最近的仰望对象。具体地,奶牛 ii 的仰望对象是满足 j>ij > i 且 hj>hih_j > h_i 的最小的 jj;若不存在这样的 jj,则奶牛 ii 没有仰望对象。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦105)n \left(1 \leqq n \leqq 10^5\right) 代表奶牛的数量。

\hspace{15pt}此后 nn 行,第 ii 行输入一个整数 hi(1≦hi≦106)h_i \left(1 \leqq h_i \leqq 10^6\right) 代表第 ii 头奶牛的身高。

输出格式

\hspace{15pt}输出 nn 行,第 ii 行输出一个整数,代表奶牛 ii 的最近的仰望对象的编号;若奶牛 ii 没有仰望对象,则输出 00。

测试样例

6
3
2
6
1
1
2
3
3
0
6
6
0

样例 1 解释

\hspace{15pt}这 66 头奶牛的身高依次为 3,2,6,1,1,23, 2, 6, 1, 1, 2,逐头奶牛分析如下:

∙ \hspace{23pt}\bullet\,奶牛 11 的身高为 33。奶牛 22 的身高为 22,并不比它高;奶牛 33 的身高为 66,比它高。因此奶牛 11 最近的仰望对象是奶牛 33;

∙ \hspace{23pt}\bullet\,奶牛 22 的身高为 22。奶牛 33 的身高为 66,比它高,因此最近的仰望对象是奶牛 33;

∙ \hspace{23pt}\bullet\,奶牛 33 的身高为 66。它右侧的奶牛身高都不超过 66,没有仰望对象;

∙ \hspace{23pt}\bullet\,奶牛 44 的身高为 11。奶牛 55 的身高为 11,并不比它高;奶牛 66 的身高为 22,比它高,因此最近的仰望对象是奶牛 66;

∙ \hspace{23pt}\bullet\,奶牛 55 的身高为 11。奶牛 66 的身高为 22,比它高,因此最近的仰望对象是奶牛 66;

∙ \hspace{23pt}\bullet\,奶牛 66 的身高为 22。它右侧没有奶牛,没有仰望对象。

\hspace{15pt}因此答案为 3,3,0,6,6,03, 3, 0, 6, 6, 0。

5
4
1
3
3
5
5
3
5
5
0

样例 2 解释

\hspace{15pt}这 55 头奶牛的身高依次为 4,1,3,3,54, 1, 3, 3, 5:

∙ \hspace{23pt}\bullet\,奶牛 11 仰望奶牛 55,因为奶牛 2,3,42, 3, 4 都不比它高,而奶牛 55 比它高;

∙ \hspace{23pt}\bullet\,奶牛 22 仰望奶牛 33,因为奶牛 33 是它右侧第一头比它高的奶牛;

∙ \hspace{23pt}\bullet\,奶牛 33 与奶牛 44 身高相同,都不满足“比它高”,因此奶牛 33 仰望奶牛 55;

∙ \hspace{23pt}\bullet\,奶牛 44 同样仰望奶牛 55;

∙ \hspace{23pt}\bullet\,奶牛 55 右侧没有奶牛,没有仰望对象。

提示

\hspace{15pt}对于 20%20\% 的数据,1≦n≦101 \leqq n \leqq 10。

\hspace{15pt}对于 50%50\% 的数据,1≦n≦1031 \leqq n \leqq 10^3。

\hspace{15pt}对于 100%100\% 的数据,1≦n≦1051 \leqq n \leqq 10^5,1≦hi≦1061 \leqq h_i \leqq 10^6。