3734 - 后面第一个大于
Description

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

Input

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

Output

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

Examples

Input

8
73 74 75 71 69 72 76 73

Output

1 1 4 2 1 1 0 0
Hint

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

Source
51nod 2500
Tags
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过次数 1