题目描述

小红发布了n个笔记，每个笔记的点赞数为ai。小红观察到，每隔一段时间，某个笔记的点赞数就会加1。但是不会出现一个笔记点赞数连续增加的情况。也就是说，一个笔记赞数加1后，下一个加1的必然是另一个笔记。

现在小红想知道，对于每一个笔记，其赞数变成所有笔记赞数最多时，此时所有的笔记赞数之和的最小值是多少？

输入描述

第一行输入一个正整数n（1 <= n <= 105），代表笔记的数量。

第二行输入n个正整数ai（1 <= ai <= 109），代表每个笔记当前的赞数。

输出描述

输出n行，每行输出一个整数，代表第i个笔记变成所有笔记赞数最多时，此时所有的笔记赞数之和的最小值。 特殊的，如果第i个笔记永远无法变成赞数最多，则输出-1。

输入示例

3
3 1 4

输出示例

9
15
8

提示信息

对于第一个笔记，当它赞数加1时，赞数达到了4，变成所有笔记赞数最多，此时赞数之和为4+1+4=9。

对于第二个笔记，可以有以下增长方式:2->1->2->1->2->3->2，此时三个笔记的赞数都是5，赞数之和为15。

对于第三个笔记，初始时它的赞数就是最多，此时赞数之和为3+1+4=8。

时间限制：c/c++：1s；java/go：3s；其他语言：6s。