题目描述

给定由 $n$ 个整数构成的数组 $\{a_1, a_2, \cdots, a_n\}$ ，从数组的第二个元素至倒数第二个元素，若存在 $a_{i - 1} < a_i$ 且 $a_i > a_{i + 1}$ ，则称位置 $i$ 是一个“山峰” ，该山峰的高度 $h_i$ 计算公式为：$h_i = a_i - \lfloor\frac{a_{i - 1} + a_{i + 1}}{2}\rfloor$ 。

需找出数组中高度最高的山峰并返回其高度。若数组中不存在任何山峰，则输出 $-1$ 。

输入格式

• 第一行输入一个正整数 $n$（$1 \leq n \leq 10^5$ ），表示数组中的元素数量。
• 第二行输入 $n$ 个正整数 $a_1, a_2, \cdots, a_n$（$1 \leq a_i \leq 10^9$ ），代表数组中的元素。

输出格式

• 若不存在任何山峰，直接输出 $-1$ ；否则，输出一个整数，代表高度最高山峰的高度。

示例

输入

5
14 15 1 10 1

输出

9