Принцеса влаштовує вечірку в своєму одновимірному королівстві, і вона хоче, щоб усі гості відчували себе комфортно. Наразі на вечірку збирається $N$ гостей, позначених як Гість $1$ до Гостя $N$. Кожен гість знаходиться на відповідній координаті $A_i$ на числовій вісі. При цьому $A_1 < A_2 < A_3 < \cdots < A_N$, і всі $A_i$ --- парні числа.

Принцеса планує вечірку протягом $k$ секунд. Протягом цього часу кожен гість може вільно рухатися по числовій вісі зі швидкістю не більше $1$ за секунду. (Також дозволяється рухатися в негативному напрямку з дотриманням обмеження на швидкість.) Гості вимагають, щоб задовольнялася наступна умова для кожного цілого числа $i$, такого що $1 \le i < N$:

Існує принаймні один момент під час вечірки (включаючи момент завершення), коли Гість $i$ та Гість $i+1$ перебувають на одній координаті. Знайдіть мінімальне $k$, для якого існує стратегія, яку можуть вжити гості, щоб задовольнити всі умови. Ми можемо довести, що відповідь є цілим числом за обмеженнями цієї задачі.

Input Specification

У першому рядку вхідних даних дається число $N$ ($2 \le N \le 2 \times 10^5$).

У другому рядку вхідних даних задається послідовність $N$ чисел $A_1, A_2, \ldots, A_N$ ($0 \le A_i \le 10^9$).

Output Specification

Виведіть відповідь у вигляді цілого числа.

Sample Input 1

3
0 6 10

Sample Output 1

5

Sample Input 2

5
0 2 4 6 8

Sample Output 2

3

Sample Input 3

10
0 2 4 6 8 92 94 96 98 100

Sample Output 3

44