单调栈
时间限制:1秒 内存限制:256M
【问题描述】
给出项数为 \(n\) 的整数数列 \(a_1..a_n\)。定义函数 \(f(i)\) 代表数列中第 \(i\) 个元素之后第一个大于 \(a_i\) 的元素的下标,即 \(f(i)=min\{ j\ |\ i<j≤n\ 且\ a_j>a_i \}\)。若不存在,则 \(f(i)=0\)。
试求出 \(f(1)..f(n)\) 的值。
【输入格式】
第一行一个正整数 \(n\)。
接下来的 \(n\) 行,每行一个整数,分别别表示正整数 \(a_1..a_n\)。
【输出格式】
\(n\) 行,每行一个整数,分别表示 \(f(1)..f(n)\) 的值。
【输入输出样例】
Input
5
1
4
2
3
5
Output
2
5
4
5
0
【数据限制】
对于 \(30\%\) 的数据,\(n≤100\)
对于 \(50\%\) 的数据,\(n≤5×10^3\)
对于 \(100\%\) 的数据,\(1≤n≤3×10^5\),\(1≤a_i≤10^9\)
【来源】
Mr.he