【题目描述】

LazyChild在青岛二中科技楼里种了一排n棵树，每棵树都有一个高度。他会枚举所有的区间，然后从区间中找出一个高度最矮的树进行浇水（照顾弱者）。由于LazyChild浇完水之后就精疲力竭了，所以请你帮助他计算每棵树都被浇了几次水。

【输入文件】

第一行一个整数n。

第二行n个整数，分别表示每棵树的高度。

【输出文件】

一行n个整数用空格隔开，分别表示每棵树被浇了几次水。

【样例输入】

3
1 3 5

【样例输出】

3 2 1

【样例解释】

LazyChild枚举到了6个区间分别是[1], [3], [5], [1 3], [3 5], [1 3 5]，对应的最矮的树的高度是1, 3, 5, 1, 3, 1。

【数据规模和约定】

对于40%的数据，n <= 1000

对于100%的数据，n <= 1000000，保证每棵树的高度都不相同