奇妙跳跃

• 时间限制：5 秒
• 内存限制：128 MiB

题目描述

给定长度为 $n$ 的正整数数组 $a$。从位置 $i$ 跳到位置 $j$（$1\le i\le j\le n$）需要支付

枚金币。

对每个 $k=1,2,\ldots,n$，求从位置 $1$ 经若干次跳跃到达位置 $k$ 所需的最少金币数。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出 $n$ 个整数，第 $k$ 个整数表示从位置 $1$ 到位置 $k$ 的最小费用。

样例输入 1

3
2 1 3

样例输出 1

0 1 2

样例输入 2

4
1 4 4 4

样例输出 2

0 1 4 8

数据范围

$2\le n\le4\cdot10^5$，$1\le a_i\le n$。

说明

答案可能超过 32 位有符号整数范围，请使用 64 位整数。