分数: 366 分
问题陈述
高桥已排队 N 多米诺骨牌连续。他们有编号 1, 2, \ldots, N 从左到右,每张多米诺骨牌 i 有一个正整数 A_i 代表其“高度”。
在这个世界的多米诺骨牌倒塌中,一张倒下的多米诺骨牌会与紧邻其右侧最近的仍然站立的多米诺骨牌相撞,如果另一张多米诺骨牌的高度严格小于自己的高度,它也会将该多米诺骨牌推倒。具体来说,该链按照以下规则进行:
- 当多米诺骨牌 i 倒下,让多米诺骨牌 j 是右侧的多米诺骨牌 i 尚未倒下的数量最少的多米诺骨牌(即,紧邻多米诺骨牌右侧最近的仍然站立的多米诺骨牌) i).
- 如果这样的多米诺骨牌 j 存在并且 A_j < A_i (多米诺骨牌的高度 j is 严格小于 多米诺骨牌的高度 i),然后是多米诺骨牌 i 推倒多米诺骨牌 j。随后,从新倒下的多米诺骨牌开始应用相同的规则 j。也就是说,使用多米诺骨牌 j的身高 以 A_j 为参考,判断右侧下一张静止的多米诺骨牌能否被推倒。
- 如果多米诺骨牌右侧没有静止的多米诺骨牌 i,或者如果多米诺骨牌的高度 j 大于或等于多米诺骨牌的高度 i (A_j \geq A_i),链条停在那里。
高桥按顺序用手指进行推倒多米诺骨牌的操作 1, 2, \ldots, N,仅当每个尚未掉落时才推动它。如果它已经倒下,他什么都不做,继续移动下一张多米诺骨牌。当他用手指推动多米诺骨牌时,从该多米诺骨牌开始应用上述链式法则。
所有多米诺骨牌倒下后,对于每张多米诺骨牌 i (1 \leq i \leq N),确定多米诺骨牌的直接原因 i 掉落。如果多米诺骨牌 i 被另一张多米诺骨牌的链条撞倒了 k (即多米诺骨牌 i 多米诺骨牌后立即倒下 k 按照上述规则倒下),输出多米诺骨牌的数量 k。如果高桥直接用手指按下去,输出 0.
约束
- 1 \leq N \leq 5 \times 10^5
- 1 \leq A_i \leq 10^9
- 所有输入均为整数。
输入
N A_1 A_2 \ldots A_N
- 第一行包含一个整数 N 代表多米诺骨牌的数量。
- 第二行包含 N 整数 A_1, A_2, \ldots, A_N 以空格分隔,代表每张多米诺骨牌的高度。
输出
输出 N 单行上用空格分隔的整数。的 i- 第一个整数是直接引发多米诺骨牌的多米诺骨牌数量 i 掉落(或 0 如果高桥直接推下去的话)。
示例输入 1
5 5 3 4 2 1
示例输出 1
0 1 0 3 4
示例输入 2
3 2 2 1
示例输出 2
0 0 2
示例输入 3
12 10 7 6 8 5 4 9 3 3 2 11 1
示例输出 3
0 1 2 0 4 5 0 7 0 9 0 11
示例输入 4
30 100 90 80 85 70 60 50 75 74 73 20 21 19 18 200 150 160 140 130 120 110 111 109 108 50 49 48 47 46 45
示例输出 4
0 1 2 0 4 5 6 0 8 9 10 0 12 13 0 15 0 17 18 19 20 0 22 23 24 25 26 27 28 29
示例输入 5
1 1000000000
示例输出 5
0