#P5788. 【模板】单调栈

【模板】单调栈

题目背景

模板题,无背景。

2019.12.12 更新数据,放宽时限,现在不再卡常了。

题目描述

给出项数为 nn 的整数数列 a1na_{1 \dots n}

定义函数 f(i)f(i) 代表数列中第 ii 个元素之后第一个大于 aia_i 的元素的下标,即 f(i)=mini<jn,aj>ai{j}f(i)=\min_{i<j\leq n, a_j > a_i} \{j\}。若不存在,则 f(i)=0f(i)=0

试求出 f(1n)f(1\dots n)

输入格式

第一行一个正整数 nn

第二行 nn 个正整数 a1na_{1\dots n}

输出格式

一行 nn 个整数 f(1n)f(1\dots n) 的值。

5
1 4 2 3 5
2 5 4 5 0

提示

【数据规模与约定】

对于 30%30\% 的数据,n100n\leq 100

对于 60%60\% 的数据,n5×103n\leq 5 \times 10^3

对于 100%100\% 的数据,1n3×1061 \le n\leq 3\times 10^61ai1091\leq a_i\leq 10^9