Arithmetic Progression

Time limit2sMemory limit128 MB

Summary

Given a sequence S and starting value A0, find the smallest common difference d >= 0 of an arithmetic progression so that floor(A0+(i+1)d) equals S_i for every index.

Level: Easy3 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

An arithmetic progression is a sequence in which the difference between every two consecutive terms is constant. For example, 3 5 7 9 11 13 is an arithmetic progression with common difference 2. In this problem, the real-valued sequence A is defined as A_i = A_0 + i*d.

You are given a sequence S of length N. For every i with 0 <= i < N, it must satisfy S_i = floor(A_{i+1}), and S is nondecreasing. Here, floor(x) is the greatest integer less than or equal to x. For example, floor(3.4) = 3, floor(0.6) = 0, floor(-1.2) = -2, and floor(-0.6) = -1.

Find the smallest possible value of d satisfying these conditions. The value d must be at least 0.

Input

The first line contains the length N of S and the initial value A_0. The second line contains N integers, from S_0 through S_{N-1}. If N = 0, the second line is not given.

N is an integer between 0 and 50, inclusive. The absolute value of A_0 and of every element of S is at most 10^6.

Output

Print the minimum possible value of d. An absolute or relative error of at most 10^{-9} is accepted. If no such value exists, print -1.

Examples6

Example 1
Input
```
4 0
6 13 20 27
```
Expected output
```
6.75
```
Example 2
Input
```
5 1
2 3 4 5 6
```
Expected output
```
1.0
```
Example 3
Input
```
0 3
```
Expected output
```
0.0
```
Example 4
Input
```
5 3
3 3 3 3 4
```
Expected output
```
0.2
```
Example 5
Input
```
1 1
-3
```
Expected output
```
-1
```
Example 6
Input
```
2 0
6 14
```
Expected output
```
-1
```