思路

• 设从 $i$ 向右行驶的每一步电量改变量为 $\Delta_k=a_k-a_{k+1}$。从 $i$ 出发到 $j$ 的前缀和为 $\sum_{t=i}^{j-1}(a_t-a_{t+1})=a_i-a_j$（望文生义的“望远镜求和”）。

• 为使过程中电量不为负，初始电量需至少抵消最小前缀和：

  • 向右所需：$\max\bigl(0,\ \max_{j\in[i,n]} a_j - a_i\bigr)$
  • 向左所需：$\max\bigl(0,\ \max_{j\in[1,i]} a_j - a_i\bigr)$

• 题目要求到达任意一端的最小初始电量，即二者取最小：

  

题目内容

给定一个长度为 $n$ 的山脉序列 $a=${ $a_1,a_2,…,a_n$ }，其中第 $i$ 个元素 $a_i$ 表示第 $i$ 座山的高度。电动汽车可以从任意位置 $i$ 出发，选择一直向左或一直向右行驶，直到山脉的端点。

行驶规则如下，当从一座高度为 $h$ 的山行驶到相邻一座高度为 $h_1$ 的山时：

• 若 $h_1 ≥ h_2$ (下坡)，电量增加 $h_1 -h_2$ ;

• 若 $h_1 < h_2$ (上坡)，电量消耗 $h_2 -h_1$ 。

对于每一个可能的出发点 $i(1 ≤i≤n)$ ，你需要分别计算，若选择从 $i$ 出发并一直向左行驶，或从 $i$ 出发并一直向右行驶，两种情况下为了保证行驶过程中电量始终不为负，所需的最小初始电量。

输入描述

第一行输入一个整数 $n(1 ≤n≤ 10^5)$ ，表示山脉序列的长度。

第二行输入 $n$ 个整数 $a_1,a_2,···,a_n(0≦a_i≦10^9)$ ，表示山脉的高度。

输出描述

输出一行 $n$ 个整数，用空格隔开。第 $i$ 个整数表示从位置 $i$ 出发，到达任意一端所需的最小初始电量。

样例1

输入

5
3 1 2 2 3

输出

0 2 1 1 0