P3616.第2题-电动汽车爬山
题目内容
给定一个长度为 n 的山脉序列 a={ a1,a2,…,an }，其中第 i 个元素 ai 表示第 i 座山的高度。电动汽车可以从任意位置 i 出发，选择一直向左或一直向右行驶，直到山脉的端点。
行驶规则如下，当从一座高度为 h 的山行驶到相邻一座高度为 h1 的山时：
对于每一个可能的出发点 i(1≤i≤n) ，你需要分别计算，若选择从 i 出发并一直向左行驶，或从 i 出发并一直向右行驶，两种情况下为了保证行驶过程中电量始终不为负，所需的最小初始电量。
输入描述
第一行输入一个整数 n(1≤n≤105) ，表示山脉序列的长度。
第二行输入 n 个整数 a1,a2,⋅⋅⋅,an(0≦ai≦109) ，表示山脉的高度。
输出描述
输出一行 n 个整数，用空格隔开。第 i 个整数表示从位置 i 出发，到达任意一端所需的最小初始电量。
样例1
输入
5
3 1 2 2 3
输出
0 2 1 1 0
