An atom of element X can exist in n distinct states with energies E_1 < E_2 < ... < E_{n}. 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:   initially the atom is in the state i, we spend E_{k} - E_{i} energy to put the atom in the state k, the atom emits a photon with useful energy E_{k} - E_{j} and changes its state to the state j, the atom spontaneously changes its state to the state i, losing energy E_{j} - E_{i}, the process repeats from step 1. 

Let's define the energy conversion efficiency as $\eta = \frac{E_{k} - E_{j}}{E_{k} - E_{i}}$, 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 E_{k} - E_{i} ≤ 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 ≤ 10^5, 1 ≤ U ≤ 10^9) — the number of states and the maximum possible difference between E_{k} and E_{i}.

The second line contains a sequence of integers E_1, E_2, ..., E_{n} (1 ≤ E_1 < E_2... < E_{n} ≤ 10^9). It is guaranteed that all E_{i} 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 $\frac{|a - b|}{\operatorname{max}(1,|b|)} \leq 10^{-9}$.


-----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 $\eta = \frac{5 - 3}{5 - 1} = 0.5$.

In the second example choose states 4, 5 and 9, so that the energy conversion efficiency becomes equal to $\eta = \frac{24 - 17}{24 - 16} = 0.875$.

Difficulty: interview

Starter code:

Solutions:
def read_data():
    n, m = map(int, input().strip().split())
    a = list(map(int, list(input().strip().split())))
    return n, m, a

def find(start,end,v):
    mid = int((start + end) / 2)
    if start == end:
        return start
    if end - start == 1:
        if a[end] <= v:
            return end
        else:
            return start
    if a[mid] == v:
        return mid
    if a[mid] > v:
        return find(start,mid,v)
    else:
        return find(mid,end,v)

def solve():
    val = -1
    for i in range(0,len(a)-2):
        pos = find(i+2,len(a)-1,a[i]+m)
        if a[pos] <= a[i] + m:
            if (a[pos] - a[i+1]) / (a[pos] - a[i]) > val:
                val = (a[pos] - a[i+1]) / (a[pos] - a[i])
    return val

n, m, a = read_data()
print(solve())

import heapq
from bisect import bisect_left, bisect_right
from collections import Counter
from collections import OrderedDict
from collections import deque
from itertools import accumulate, product

import math

R = lambda: map(int, input().split())

n, u= R()
arr = list(R())
res = -1
for l in range(n):
    r = bisect_right(arr, arr[l] + u) - 1
    if r - l > 1:
        res = max(res, (arr[r] - arr[l + 1]) / (arr[r] - arr[l]))
print(res)

n,m=list(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)



# Made By Mostafa_Khaled


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

import sys

string = sys.stdin.readline()
n = int(string.split()[0])
u = int(string.split()[1])
levels = tuple(map(int, sys.stdin.readline().split()))
if len(levels) < 3:
    sys.stdout.write('-1')
    return

i, j, k = 0, 1, 2
indices = (0, 1, 2)
level_i = levels[0]
level_j = levels[1]
nu = levels[2] - level_i
"""
if nu <= u:
    nu = (levels[2] - level_j) * 1 / nu
else:
    nu = -1
"""
nu = -1
while i < n - 2:
    while k < n - 1 and levels[k + 1] - level_i <= u:
        k += 1
    nu_cur = levels[k] - level_i
    if nu_cur <= u:
        nu_cur = (levels[k] - level_j) * 1 / nu_cur
    else:
        nu_cur = -1
    if nu_cur > nu:
        nu = nu_cur
        indices = (i, j, k)
    i += 1
    j += 1
    k = max(k, j + 1)
    level_j = levels[j]
    level_i = levels[i]

sys.stdout.write(str(nu))




import sys

string = sys.stdin.readline()
n = int(string.split()[0])
u = int(string.split()[1])
levels = tuple(map(int, sys.stdin.readline().split()))
if len(levels) < 3:
    sys.stdout.write('-1')
    return

i, j, k = 0, 1, 2
indices = (0, 1, 2)
level_i = levels[0]
level_j = levels[1]
nu = levels[2] - level_i
nu = -1
while i < n - 2:
    while k < n - 1 and levels[k + 1] - level_i <= u:
        k += 1
    nu_cur = levels[k] - level_i
    if nu_cur <= u:
        nu_cur = (levels[k] - level_j) * 1 / nu_cur
    else:
        nu_cur = -1
    if nu_cur > nu:
        nu = nu_cur
        indices = (i, j, k)
    i += 1
    j += 1
    k = max (k, j + 1)
    level_j = levels[j]
    level_i = levels[i]

sys.stdout.write(str(nu))




n, v = list(map(int, input().split()))
l = list(map(int, input().split()))
ans = [-1]
for i in range(n - 2):
    uk1 = i + 2
    uk2 = n - 1
    while (uk2 - uk1 > 1):
        if l[(uk2 + uk1) // 2] - l[i] <= v:
            uk1 = (uk2 + uk1) // 2
        else:
            uk2 = (uk2 + uk1) // 2
    if l[uk2] - l[i] <= v:
        ans.append((l[uk2] - l[i + 1]) / (l[uk2] - l[i]))
    elif l[uk1] - l[i] <= v:
        ans.append((l[uk1] - l[i + 1]) / (l[uk1] - l[i]))
print(max(ans))

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)

from bisect import bisect_left
n, u = map(int, input().split())
arr = [int(x) for x  in input().split()]
ans = -1
for i in range(n-2):
    bi = bisect_left(arr, arr[i] + u)
    if bi == n: bi -= 1
    if bi == i+1: continue
    if arr[bi] - u > arr[i]: bi -= 1
    if i == bi or i+1 == bi: continue
    #print(arr[i], arr[i+1], arr[bi])
    ans = max(ans, (arr[bi] - arr[i+1])/(arr[bi] - arr[i]))
print(ans)

import bisect


n,u=list(map(int,input().split()))
ans=float(-1)
a=list(map(int,input().split()))
for i in range(0,n-2,1):
    x=int(bisect.bisect_left(a,a[i]+u+1))
    x=x-1
    if a[x]!=a[i] and a[x]!=a[i+1]:
        ans=max(ans,(a[x]-a[i+1])*1.0/(a[x]-a[i]))
print(ans)


from sys import stdin, stdout

n, U = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

k = 0
ans = -1
for i in range(n):
    while k+1 < n and a[k+1] - a[i] <= U:
        k += 1
    if k - i < 2:
        continue
    j = i+1
    cur = (a[k] - a[j]) / (a[k] - a[i])
    ans = max(ans, cur)
print(ans)

from bisect import bisect_left as bi
n,u=list(map(int,input().split()))
a=list(map(int,input().split()))
a.sort()
c=[]
for i in range(n-1):
    b=bi(a,a[i]+u)
    if b!=n:
        if a[b]==a[i]+u:
            b=b+1
    b=a[b-1]
    if b-a[i]!=0:
        c.append((b-a[i+1])/(b-a[i]))
if len(c)==0 or max(c)==0:
    print(-1)
else:
    print(max(c))

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)