题目描述

军队每从一个国家移动到一个相邻国家就需要消耗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次