思路

反悔贪心。 考虑当前在第 i 个城市，即将前往第 i+1 个城市，手上没有粮食，需要在第 [1, i] 个城市中选择一个城市购买1单位。

Q：应该选择哪个呢？

A：要求花费最少，所以选择粮食价格最低的那个城市

Q：如果有多个城市的花费都一样最低呢？

题目描述

军队每从一个国家移动到一个相邻国家就需要消耗1单位的粮食，每个国家都会售卖粮食，每单位价格为$a_i$，小红可以购买任意单位的粮食。 小红想要用最少的花费使得军队到达$n$号国家，但是她希望每个国家的粮食不要购买太多，即重复吃一个国家粮食的次数的最大值最小。 小红想知道一种她要到达$n$号国家且满足上述条件的粮食购买方案。(如果有多种答案，可以输出任意一种)

输入描述

第一行输入一个整数$n(1\le n\le 10^5)$表示国家个数。 第二行输入$n$个整数表示每个国家的粮食售价 $a(1\le a_i\le 10^5)$

输出描述

输出一行整数表示答案

样例

输入

4
1 2 1 4

输出

2 0 1 0

说明

在第1个国家购买2单位粮食花费2.
在第2个国家购买0单位粮食花费0.
在第3个国家购买1单位粮食，花费1。
在第4个国家购买0单位粮食，花费0。此时花费为3，吃同一种粮食次数最多的1号国家的粮食，为2次