3734 - 后面第一个大于
描述

小b有一个长度为 n 的序列 t,现在她对于每个 i,求最小的正数 j 满足 i+j <= n 且 t[i+j] > t[i],输出 j,如果不存在这样的 j,则输出 0。

输入

第一行输入一个数 n;
第二行输入 n 个数 t1-tn,以空格隔开;
其中 1 <= n <= 30000,对于任意 t[i] 满足 30 <= t[i] <= 100。

输出

输出一行 n 个数,第 i 个数表示 i 的答案。

样例

输入

8
73 74 75 71 69 72 76 73

输出

1 1 4 2 1 1 0 0
提示

从右往左扫描,维护一个单调递减的栈(栈中保存下标,越靠近栈顶的值越小)。插入当前位置 i 前,不断弹出栈中值小于等于 t[i] 的下标,此时栈顶就是 i 后面第一个比它大的位置,答案即栈顶下标减 i;栈空则答案为 0。总复杂度 O(n)。

来源
51nod 2500
标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过次数 1