You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

不难

题目描述

给定n个数如果这n个数满足$a_1$>=$a_2$,$a_3$>=$a_4$,$a_5$>=$a_6$.......$a_n$$_-$$_1$>=$a_n$且每个数都大于等于0这样的n个数我们称为两两递减数组，反之如果这n个数满足$a_1$<=$a_2$,$a_3$<=$a_4$,$a_5$<=$a_6$.......$a_n$$_-$$_1$<=$a_n$且每个数都大于等于0我们称为两两递增数组，请问是否存在一个数k,使得两两递减数组中每两个数中如（$a_1$>=$a_2$）,（$a_3$>=$a_4$）符号左边的数减去k,右边的数加上k使得最后这n个数变为两两递增数组（每两个数之间只能进行这样的操作一次且每个数都要被减k或加k）,如$a_1$和$a_2$进行一次加减k后变为:$a_1$-k,$a_2$+k，同理$a_3$$a_4$进行一次加减k后变为:$a_3$-k,$a_4$+k。如果存在请输出满足条件的最小的k，如果不存在则输出-1。

输入格式

第一行输入一个数n。

第二行输入n个数第i个元素为$a_i$。

数据保证输入的n个数满足两两递减数组的条件，且n为偶数。

输出格式

输出一行如果存在最小数k则输出k否则输出-1.

样例

样例1

4
6 2 7 4

2

样例2

6
8 2 7 4 2 1

-1

样例3

6
8 2 5 1 3 2

3

限制

对于100%的数据，2<=n<=$10^6$,0<=k<=$10^4$,1<=$a_i$<=$10^9$。

时限:1s 内存:256mb