問題文
甜甜圈镇有一家超级受欢迎的甜甜圈店,每天都排着长队。这家甜甜圈店现在 N 人们站成一条直线。排队等候的人们担心甜甜圈还没轮到就卖完了。一家甜甜圈店的经理决定计算每个人的“焦虑程度”,这代表了他们的焦虑程度。
从前面 i 番目 (1 ≦ i ≦ N) 我们称之为 i 。人 i 的高度是 H_i 。人 i 的“焦虑水平”是“人类 i 是您向前看时可以看到的人数。人 当 i 向前看时 j 可见的条件如下。
- 人 i 比人 j 位于队伍的最前面。也就是说,j < i 。
- 人 i 和人 j 之间的人 j 没有人比我高。也就是说, 使其满足j < k < i 和 所有满足 H_j < H_k 喜欢满足 k 不存在。
例如,队列中人员的身高从前面按顺序显示。 2,5,3,4,1 然后是队伍后面的人 当 5 看向前方时,他看到的人是一个人。 2 和人 4 的 2 因为它是一个人,所以它是一个人。 5 的“焦虑程度”是 2 。
入力
输入将以以下格式从标准输入提供。
N H_1 H_2 ... H_N
- 1 行包含一个表示队列中人数的整数。 N (1 ≦ N ≦ 10^5) 。 来自行
- 2 队列中人员的身高显示在行中。 N 整数由空格分隔。其中 i 第一个整数 H_i (1 ≦ H_i ≦ 10^6) 是一个人 表示 i 的高度。然而, 当p \neq q 什么时候 H_p \neq H_q 有保证。
部分点
针对此问题设置了部分分数。
- N ≦ 100 的测试用例都得到正确回答, 10 点。 如果您正确回答
- N ≦ 5000 的测试用例都得到正确回答, 40 点。 如果您正确回答
出力
输出是 由 N 行组成。其中 i 在该行中,该人 代表 i 的“焦虑程度” 打印 1 整数。还在输出末尾添加换行符。
入力例1
5 2 5 3 4 1
出力例1
0 1 1 2 2
入力例2
1 1000000
出力例2
0
入力例3
8 66 52 56 32 27 50 72 23
出力例3
0 1 2 2 3 4 3 1