题目描述

ycy 是 ACM 财阀的老大，从前代老大手中继承了一笔巨大的财产。但是！他的真实身份是，cy 教派的教皇！他暗中用这笔财产，购置多处房产，把房产分配给自己得力的下属，用于壮大 cy 教的势力。为了让整个教派都能掌握在自己手中，他希望能够直接看到自己手下爪牙住的房子。 ycy 想知道自己购置的这批房产可以供他安插多少爪牙。由于教皇日理万机，就把这个任务交给了红衣主教——瓜瓜。

瓜瓜收到这个任务的时候，不禁冒了一身冷汗。实验室的大家都觉得瓜瓜很厉害，只有瓜瓜自己知道实际上自己只是个小菜瓜。一天一天的过去，瓜瓜还是没法解决这个问题。瓜瓜不想让自己是菜瓜的事实暴露给教皇，于是找到了你帮他解决这个问题。

为了简化问题，我们考虑事件发生在一个二维平面上。第 $i$ 栋楼房的高度为 $h_i$，可以用一条 $(i,0)$ 到 $(i,h_i)$ 的线段表示。教皇站在第 $i$ 栋楼房的楼顶（忽略身高），如果第 $j$ 栋楼房上任何一个高度大于 $0$ 的点与 $(0,h_i)$ 到 $(0,h_j)$ 的连线没有与其他所有楼房的线段相交，那么这栋楼房就被认为是可见的。

输入格式

第一行有一个整数 $n(1 \leqslant n \leqslant 3000)$ ，表示数轴上有 $n$ 栋房子。

第二行有 $n$ 个整数，第 $i$ 个数字 $h_i$ 表示位置 $i$ 楼房的高度。其中 $1 \leqslant h_i \leqslant 10^6$。

输出格式

在一行输出 $n$ 个数字，用空格分开，分别表示每个位置能够看到多少栋楼房。

样例

4
2 3 3 5

1 3 2 2

4
2 3 10 100

3 3 3 3

提示

如下图所示， 第一个点只能看到一栋楼房，输出 $1$。剩下三个点可以由图得到 3 2 2。