问题描述

高桥同学是一名登山家，他正在攀登一座山脉。

这座山脉上有 $N$ 个山小屋，沿着东西方向成直线排列，每个山小屋从西到东按顺序编号为 $1$ 到 $N$。

第 $i$ 个山小屋建在海拔 $h_i$ 的地方。

高桥同学想知道从每个山小屋能看到多少个山小屋。

第 $i$ 个山小屋能看见第 $j$ 个山小屋的条件是，它们之间的所有山小屋和第 $j$ 个山小屋的海拔都不超过 $h_i$。

请计算每个山小屋能看见的山小屋数量。

注意，从第 $i$ 个山小屋看到的山小屋数量不包括第 $i$ 个山小屋本身。

---

输入

输入以以下格式从标准输入中读取：

$N$ $h_1$ $h_2$ : $h_N$

• 第 1 行为山小屋的个数 $N (1 ≤ N ≤ 10^5)$。
• 第 2 行开始的 $N$ 行，其中第 $i$ 行表示第 $i$ 个山小屋的海拔 $h_i (1 ≤ h_i ≤ 10^5)$。

部分分

本问题设置了部分分。

• 对于满足 $1 ≤ N ≤ 3,000$ 的数据集，如果程序能给出正确的答案，将获得 30 分。
• 对于满足 $1 ≤ N ≤ 10^5$ 的数据集，如果程序能给出正确的答案，将获得额外的 70 分。总共可获得 100 分。

输出

输出包含 $N$ 行，第 $i$ 行表示从第 $i$ 个山小屋可以看到的山小屋数量。

---

输入示例1

3
1
2
3

输出示例1

0
1
2

任何山小屋只能看到它自身以西的所有山小屋。

---

输入示例2

5
1
2
3
2
1

输出示例2

0
1
4
1
0

山小屋 $1$ 和 $5$ 都无法看到其他山小屋。山小屋 $2$ 可以看到山小屋 $1$。山小屋 $4$ 可以看到山小屋 $5$。山小屋 $3$ 可以看到除了自身以外的所有山小屋。

---

输入示例3

5
3
2
1
2
3

输出示例3

4
2
0
2
4

请注意，山小屋可以看到和它自身相同高度的山小屋。

---

输入示例4

8
4
3
2
3
4
3
2
1

输出示例4

7
2
0
2
7
2
1
0

---