J. 蘑菇

描述

齐齐在魔法世界栽种了N个蘑菇，这些蘑菇沿着一条线排成一排，第i个蘑菇的高度为Ai。

齐齐不喜欢蘑菇按自己的习性乱长，他喜欢蘑菇长得整整齐齐的样子。具体来说，就是相邻的两个蘑菇，长在右边的最好不要比长在左边的矮。

齐齐可以向魔法长老借一种药水（且只能借用一种），药水能改变所有蘑菇的高度。对于第i个蘑菇，魔力值为X（X≥0）的药水会将其高度变成 |Ai-X|。

齐齐想知道，要想让自己的蘑菇如上面所述那样长得”整整齐齐“的，需要借用的药水魔力值X最小是多少？如果没有任何一种魔力值的药水能达到目标，请输出-1。

输入

第一行一个整数N;

第二行N个整数,表示N个蘑菇依次的高度Ai。

输出

输出一个整数，表示答案。

样例

cin	out
5 5 3 3 3 5	4
4 5 3 4 5	-1
6 29613295 52036613 75100585 78027446 81409090 73215	40741153