An atom of element X can exist in n distinct states with energies E1 < E2 < ... < En. Arkady wants to build a laser on this element, using a three-level scheme. Here is a simplified description of the scheme. 

Three distinct states i, j and k are selected, where i < j < k. After that the following process happens: 

  1. initially the atom is in the state i,
  2. we spend Ek - Ei energy to put the atom in the state k,
  3. the atom emits a photon with useful energy Ek - Ej and changes its state to the state j,
  4. the atom spontaneously changes its state to the state i, losing energy Ej - Ei,
  5. the process repeats from step 1. 



Let's define the energy conversion efficiency as <image>, i. e. the ration between the useful energy of the photon and spent energy.

Due to some limitations, Arkady can only choose such three states that Ek - Ei ≤ U.

Help Arkady to find such the maximum possible energy conversion efficiency within the above constraints.

Input

The first line contains two integers n and U (3 ≤ n ≤ 105, 1 ≤ U ≤ 109) — the number of states and the maximum possible difference between Ek and Ei.

The second line contains a sequence of integers E1, E2, ..., En (1 ≤ E1 < E2... < En ≤ 109). It is guaranteed that all Ei are given in increasing order.

Output

If it is not possible to choose three states that satisfy all constraints, print -1.

Otherwise, print one real number η — the maximum possible energy conversion efficiency. Your answer is considered correct its absolute or relative error does not exceed 10 - 9.

Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if <image>.

Examples

Input

4 4
1 3 5 7


Output

0.5


Input

10 8
10 13 15 16 17 19 20 22 24 25


Output

0.875


Input

3 1
2 5 10


Output

-1

Note

In the first example choose states 1, 2 and 3, so that the energy conversion efficiency becomes equal to <image>.

In the second example choose states 4, 5 and 9, so that the energy conversion efficiency becomes equal to <image>.

Difficulty: MEDIUM_HARD
Tags: Sorting

Amortized analysis

Greedy algorithms
Skill types: Sorting

Amortized analysis

Greedy algorithms
Expected Time Complexity: O(NLOG(N))

Starter code:

Solutions:
(n, u) = map(int, input().split())
a = list(map(int, input().split()))
i = 0
j = 1
f = 1
ma = -1
while not (i == j and i == n - 1):
	if j <= i:
		j += 1
	if j < n - 1:
		if a[j + 1] - a[i] <= u:
			j += 1
		else:
			if j - i >= 2:
				f = 0
				ma = max(ma, (a[j] - a[i + 1]) / (a[j] - a[i]))
			i += 1
	else:
		if j - i >= 2:
			f = 0
			ma = max(ma, (a[j] - a[i + 1]) / (a[j] - a[i]))
		i += 1
if f:
	print(-1)
else:
	print(ma)


(n, u) = map(int, input().split())
e = list(map(int, input().split()))
res = -1
k = 2
for i in range(n - 2):
	j = i + 1
	k = max(k, j + 1)
	while k < n and e[k] - e[i] <= u:
		k += 1
	k -= 1
	if k > j:
		res = max(res, (e[k] - e[j]) / (e[k] - e[i]))
print(res)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
c = 0
ans = -1
for i in range(n - 1):
	while c < n - 1 and a[c + 1] - a[i] <= m:
		c += 1
	if i < c - 1:
		ans = max(ans, (a[c] - a[i + 1]) / (a[c] - a[i]))
print(ans)


(n, U) = map(int, input().split())
E = [int(x) for x in input().split()]
E.append(10 ** 100)
k = 0
best = -1
for i in range(n):
	while E[k + 1] - E[i] <= U:
		k += 1
	j = i + 1
	if i < j < k:
		best = max(best, (E[k] - E[j]) / (E[k] - E[i]))
print(best)


import math, sys, bisect, heapq
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda : map(int, input().split())
alele = lambda : list(map(int, input().split()))

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])
(n, U) = ilele()
A = alele()
Ans = -1
for i in range(n - 2):
	x = A[i]
	y = x + U
	z = bisect.bisect_left(A, y, lo=i + 2, hi=n)
	if z == n:
		z -= 1
	if A[z] <= x + U:
		a = A[z]
	elif A[z - 1] <= x + U and z - 1 != i + 1:
		a = A[z - 1]
	else:
		continue
	b = (a - A[i + 1]) / (a - A[i])
	Ans = max(Ans, b)
print(Ans)


import sys
[n, U] = map(int, sys.stdin.readline().strip().split())
E = list(map(int, sys.stdin.readline().strip().split()))
max_eta = -1
k = 2
for i in range(n - 2):
	k = max(k, i + 2)
	if E[k] - E[i] > U:
		continue
	while k + 1 < n and E[k + 1] - E[i] <= U:
		k += 1
	eta = (E[k] - E[i + 1]) / (E[k] - E[i])
	max_eta = max(max_eta, eta)
if max_eta < 0:
	print(max_eta)
else:
	print('{:.10f}'.format(max_eta))


(n, U) = [int(c) for c in input().split(' ')]
E = [int(c) for c in input().split(' ')]

def binary_max_search(max_limit):
	(left, right) = (0, n - 1)
	while left < right:
		mid = (left + right) // 2 + 1
		if E[mid] <= max_limit:
			(left, right) = (mid, right)
		else:
			(left, right) = (left, mid - 1)
	return left
max_conversion_rate = -1
for i in range(n - 2):
	k = binary_max_search(U + E[i])
	if k > i + 1:
		temp = (E[k] - E[i + 1]) / (E[k] - E[i])
		if temp > max_conversion_rate:
			max_conversion_rate = temp
print(max_conversion_rate)


(n, U) = map(int, input().split())
E = list(map(int, input().split()))
best = -1
k = 0
for i in range(n):
	while k + 1 < n and E[k + 1] - E[i] <= U:
		k += 1
	if k >= i + 2:
		best = max(best, (E[k] - E[i + 1]) / (E[k] - E[i]))
print(best)


(n, U) = list(map(int, input().split()))
E = list(map(int, input().split()))
ind_i = 0
prev_ind_k = ind_i + 2
maxi_efficiency = -1
turn = 0
for ind_i in range(0, n - 2):
	ind_j = ind_i + 1
	prev_ind_k = max(prev_ind_k, ind_i + 2)
	Ei = E[ind_i]
	Ej = E[ind_j]
	for ind_k in range(prev_ind_k, n + 1):
		if ind_k == n:
			prev_ind_k = n - 1
			break
		Ek = E[ind_k]
		if Ek - Ei > U:
			prev_ind_k = ind_k - 1
			break
		efficiency = (Ek - Ej) / (Ek - Ei)
		if efficiency > maxi_efficiency:
			maxi_efficiency = efficiency
print(maxi_efficiency)


import sys, math, os.path
from decimal import Decimal
FILE_INPUT = 'c.in'
DEBUG = os.path.isfile(FILE_INPUT)
if DEBUG:
	sys.stdin = open(FILE_INPUT)

def ni():
	return map(int, input().split(' '))

def nia():
	return list(map(int, input().split()))

def log(x):
	if DEBUG:
		print(x)
(n, u) = ni()
e = nia()
log(e)
mres = Decimal(-1)
iu = 0
for i in range(n):
	while iu < n - 1 and e[iu + 1] - e[i] <= u:
		iu += 1
	if i < iu - 1:
		j = i + 1
		k = iu
		enew = Decimal(e[k] - e[j]) / Decimal(e[k] - e[i])
		mres = max(enew, mres)
print(mres)


(nE, U) = [int(x) for x in input().split(' ')]
energies = [int(x) for x in input().split(' ')]
end = 0
best_ratio = -1
for beg in range(nE - 2):
	while end + 1 < nE and energies[end + 1] - energies[beg] <= U:
		end += 1
	if end - beg < 2:
		continue
	new_ratio = (energies[end] - energies[beg + 1]) / (energies[end] - energies[beg])
	best_ratio = max(best_ratio, new_ratio)
if best_ratio == -1:
	print(-1)
else:
	print('%.20f' % best_ratio)


(n, U) = list(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
import bisect

def max_eligible(a, x):
	ind = bisect.bisect_right(a, x)
	if ind <= len(a):
		return a[ind - 1]
	else:
		return -1
max_val = -1
for i in range(n - 2):
	x = a[i] + U
	val1 = max_eligible(a, x)
	if val1 != -1 and val1 != a[i + 1] and (val1 != a[i]):
		val = (val1 - a[i + 1]) / (val1 - a[i])
		max_val = max(max_val, val)
print(max_val)


(n, u) = map(int, input().split())
arr = list(map(int, input().split()))
(j, i) = (1, 0)
maxi = -1
flag = 0
for i in range(n - 1):
	if arr[i + 1] - arr[i] <= u:
		flag = 1
if flag == 0:
	print('-1')
	exit()
i = 0
while i < n - 2:
	while 1:
		if j >= n:
			j = n - 1
			break
		if arr[j] - arr[i] > u:
			j -= 1
			break
		j += 1
	if i == j:
		j += 1
	elif arr[j] == arr[i]:
		pass
	elif arr[j] - arr[i] <= u:
		maxi = max(maxi, (arr[j] - arr[i + 1]) / (arr[j] - arr[i]))
	i += 1
if maxi == 0:
	print('-1')
else:
	print(maxi)


(n, u) = map(int, input().split())
a = list(map(int, input().split()))
(l, r) = (0, 0)
ans = -1
for i in range(n):
	r = max(l, r)
	while r < n - 1 and a[r + 1] - a[l] <= u:
		r += 1
	if r - l > 1 and a[r] - a[l] <= u:
		ans = max(ans, (a[r] - a[l + 1]) / (a[r] - a[l]))
	l += 1
print(ans)


(n, u) = map(int, input().split())
e = list(map(int, input().split()))
e = sorted(e)
r = 1
ans = -1
for i in range(n - 2):
	k = e[i + 1] - e[i]
	while r < n and e[r] - e[i] <= u:
		r += 1
	pr = r - 1
	if pr - i >= 2:
		ans = max(ans, (e[pr] - e[i + 1]) / (e[pr] - e[i]))
if ans == -1:
	print(-1)
	exit()
print('%.12f' % ans)


def sss(l, r, tt):
	f = -1
	while l <= r:
		mid = l + r >> 1
		if a[mid] - a[tt] <= m:
			f = mid
			l = mid + 1
		else:
			r = mid - 1
	return f
(n, m) = map(int, input().split())
a = [int(x) for x in input().split()]
f = 0
l = len(a)
Maxx = -1
for i in range(0, l - 2):
	if a[i + 2] - a[i] <= m:
		k = sss(i + 2, l - 1, i)
		if k != -1:
			Maxx = max(Maxx, (a[k] - a[i + 1]) / (a[k] - a[i]))
if Maxx == -1:
	print(-1)
else:
	print('%.15f\n' % Maxx)


import sys

def read_two_int():
	return map(int, sys.stdin.readline().strip().split(' '))

def fast_solution(n, U, E):
	best = -1
	R = 2
	for i in range(n - 2):
		R = max(R, i + 2)
		while R + 1 < n and E[R + 1] - E[i] <= U:
			R += 1
		if E[R] - E[i] <= U:
			efficiency = float(E[R] - E[i + 1]) / (E[R] - E[i])
			if best is None or efficiency > best:
				best = efficiency
	return best
(n, U) = read_two_int()
E = list(read_two_int())
print(fast_solution(n, U, E))


(N, U) = map(int, input().strip().split())
E = list(map(int, input().strip().split()))
maxu = -1
j = 2
if N < 3:
	print(-1)
for i in range(N - 2):
	j = max(i + 2, j)
	if E[j] - E[i] > U:
		continue
	while j < N and E[j] - E[i] <= U:
		j += 1
	j -= 1
	maxu = max(maxu, (E[j] - E[i + 1]) / (E[j] - E[i]))
print(maxu)


par = input()
par = list(map(int, par.split()))
(n, U) = (par[0], par[1])
E = input()
E = list(map(int, E.split()))
f = -1
idx = 0
for i in range(n - 2):
	while idx < n - 1 and E[idx + 1] <= E[i] + U:
		idx += 1
	if idx - i < 2:
		continue
	else:
		f = max((E[idx] - E[i + 1]) / (E[idx] - E[i]), f)
print(f)


(n, U) = map(int, input().split())
Ar = list(map(int, input().split()))
R = 0
ans = -1
for i in range(n):
	while R + 1 < n and Ar[R + 1] - Ar[i] <= U:
		R += 1
	if i + 1 < R:
		ans = max((Ar[R] - Ar[i + 1]) / (Ar[R] - Ar[i]), ans)
print(ans)