题目背景

已知当山的海拔过高时，稀薄的氧气会对人体产生负担，使得人在登山时所要花费的体力更多，现有一批登山员在预备登山。

题目描述

假设原本一位登山员在登山时每登 $1$ 米要花费 $1$ 点体力，下山不花费体力，在海拔达到一定高度之后，登山员登山每登 $1$ 米要额外花费 $1$ 点体力值。

由于登山时会不断地重复上山下山，所以登山社记录了登山员的行动轨迹，其中一定包括每一次登山达到的最高点和下山达到的最低点，且假定开始和结束时登山员一定在山脚（高度为0）。

某登山社想计算出假设从所有可能的海拔高度开始额外花费体力时，所需要花费的体力的数量。（所有可能的海拔高度指从 $1$ 到最高山峰高度。）

请你计算并输出最终结果。

输入格式

两行。

第一行一个正整数 $n$ ，表示登山员行动轨迹点的数量。

第二行 $n$ 个非负数 $a_i$ ，表示登山员的行动轨迹，保证 $a_1$ 和 $a_n$ 一定是 $0$。

输出格式

一行，若干个值。表示最终结果。

样例 #1

样例输入 #1

5
0 3 1 2 0

样例输出 #1

7 5 4

提示

【样例解释】

假定海拔从 $1$ 米开始需要额外花费体力，那么从 $0$ 米登到 $3$ 米要花费的体力值为 $1+2+2 = 5$，从 $1$ 米登到 $2$ 米要花费的体力值为 $2$，因此花费的总体力值为 $7$。

假定海拔从 $2$ 米开始需要额外花费体力，那么从 $0$ 米登到 $3$ 米要花费的体力值为 $1+1+2 = 4$，从 $1$ 米登到 $2$ 米要花费的体力值为 $1$，因此花费的总体力值为 $5$。

假定海拔从 $3$ 米开始需要额外花费体力，那么从 $0$ 米登到 $3$ 米要花费的体力值为 $1+1+1 = 3$，从 $1$ 米登到 $2$ 米要花费的体力值为 $1$，因此花费的总体力值为 $4$。

【数据范围】

对于$30\%$ 的数据，$1\le n \le 10^3,1\le a_i \le 100$。

对于 $100\%$ 的数据，$1\le n \le 10^6$,$1\le a_i \le 10^6$。