Mike is trying rock climbing but he is awful at it. 

There are n holds on the wall, i-th hold is at height a_{i} off the ground. Besides, let the sequence a_{i} increase, that is, a_{i} < a_{i} + 1 for all i from 1 to n - 1; we will call such sequence a track. Mike thinks that the track a_1, ..., a_{n} has difficulty $d = \operatorname{max}_{1 \leq i \leq n - 1}(a_{i + 1} - a_{i})$. In other words, difficulty equals the maximum distance between two holds that are adjacent in height.

Today Mike decided to cover the track with holds hanging on heights a_1, ..., a_{n}. To make the problem harder, Mike decided to remove one hold, that is, remove one element of the sequence (for example, if we take the sequence (1, 2, 3, 4, 5) and remove the third element from it, we obtain the sequence (1, 2, 4, 5)). However, as Mike is awful at climbing, he wants the final difficulty (i.e. the maximum difference of heights between adjacent holds after removing the hold) to be as small as possible among all possible options of removing a hold. The first and last holds must stay at their positions.

Help Mike determine the minimum difficulty of the track after removing one hold.


-----Input-----

The first line contains a single integer n (3 ≤ n ≤ 100) — the number of holds.

The next line contains n space-separated integers a_{i} (1 ≤ a_{i} ≤ 1000), where a_{i} is the height where the hold number i hangs. The sequence a_{i} is increasing (i.e. each element except for the first one is strictly larger than the previous one).


-----Output-----

Print a single number — the minimum difficulty of the track after removing a single hold.


-----Examples-----
Input
3
1 4 6

Output
5

Input
5
1 2 3 4 5

Output
2

Input
5
1 2 3 7 8

Output
4



-----Note-----

In the first sample you can remove only the second hold, then the sequence looks like (1, 6), the maximum difference of the neighboring elements equals 5.

In the second test after removing every hold the difficulty equals 2.

In the third test you can obtain sequences (1, 3, 7, 8), (1, 2, 7, 8), (1, 2, 3, 8), for which the difficulty is 4, 5 and 5, respectively. Thus, after removing the second element we obtain the optimal answer — 4.

Difficulty: interview

Starter code:

Solutions:
def calcdiff(listx):
    maxim = -1
    for i in range(1, len(listx)):
        maxim = max(maxim, listx[i] - listx[i-1])
    return maxim
x = int(input())
t = list(map(int, input().split(' ')))
maximx = 90000001
for i in range(1, x-1):
    maximx = min(maximx, calcdiff(t[:i] + t[i+1:]))
print(maximx)
    


n = int(input())
a = list(map(int, input().split()))

def f(a):
    mm = float('-inf')
    for x in range(len(a)-1):
        mm = max(mm, a[x+1] - a[x])
    return mm

ans, ansx = -1, float('+inf')
for i in range(1, n-1):
    nn = f(a[:i]+a[i+1:])
    if nn < ansx:
        ans, ansx = i, nn
print(ansx)


def getrazn(ar):
	e = 0
	for i in range(len(ar)):
		if ar[i] - ar[i-1] > e:
			e = ar[i] - ar[i-1]
	return(e)


input()
a = list(map(int, input().split()))
ranz = []

for i in range(1,len(a)-1):
	acopy = a.copy()
	del(acopy[i])
	ranz.append(getrazn(acopy))

print(min(ranz))

n = list(map(int, input().split()))
l = list(map(int, input().split()))
ans = 1000
for i in range(1,len(l)-1):
    li = l[:]
    li.remove(l[i])
    m = 0
    for j in range(len(li)-1):
        m = max(li[j+1] - li[j], m)
    ans = min(m, ans)

print(ans)

                   


n = int(input())
line = input().split()

lst = []
for num in line:
    lst.append(int(num))

ans = lst[1] - lst[0]
mn = lst[2] - lst[0]
for i in range(2, n):
    ans = max(ans, lst[i] - lst[i - 1])
    mn = min(mn, lst[i] - lst[i - 2])

ans = max(ans, mn)
print(str(ans))


n, a = int(input()), list(map(int, input().split()))
ans = 20000
for i in range(1, n - 1):
    b = a[:i] + a[i + 1:]
    ans = min(ans, max(b[j + 1] - b[j] for j in range(n - 2)))
print(ans)


n = int(input())
d = input()
d = [int(d) for d in d.split()]
m1 = -1
m = 10000000000
for i in range(0,n-1):
    if d[i+1] - d[i] > m1:
        m1 = d[i+1] - d[i]
for i in range(1,n-1):
    if d[i+1] - d[i-1] < m:
        m = d[i+1] - d[i-1]
print(max(m,m1))
    


__author__ = 'Rakshak.R.Hegde'
"""
Created on Dec 17 2014 PM 10:02

@author: Rakshak.R.Hegde
"""

n = int(input())
a = list(map(int, input().split()))
minI = min(range(1, n - 1), key=lambda x: a[x + 1] - a[x - 1])
a.pop(minI)
maxI = max(range(1, n - 1), key=lambda x: a[x] - a[x - 1])
print(a[maxI] - a[maxI - 1])

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    bb = [b - a for b, a in zip(aa[1:], aa)]
    print(max(min(a + b for a, b in zip(bb[1:], bb)), max(bb)))


def __starting_point():
    main()

__starting_point()

holds= int(input())
heights= [int(i) for i in input().split()]
ans= 999999999
real= heights
for i in range(1, len(heights)-1):
    #print(i, heights, real)
    app= heights[i]
    heights.remove(app)
    k= 0
    for j in range(len(heights)-1):
        k= max(heights[j+1]-heights[j], k)
    
    ans= min(ans, k)
    heights.append(app)
    heights= sorted(heights)
    
print(ans)

def main():
	n = int(input())
	a =list(map(int,input().split()))
	min_max = 1000000
	max_diff = 0
	for i in range(1,n-1):
		max_diff = 0
		c = a[:i]+a[i+1:]
		for j in range(n-2):
			max_diff = max(c[j+1]-c[j],max_diff)
		#print(max_diff)
		min_max = min(max_diff,min_max)

	print(min_max)
	

def __starting_point():
	main()

__starting_point()

n, a = int(input()), list(map(int, input().split()))
i = min((a[i+2]-a[i], i,) for i in range(n-2))[1]+1
a = a[:i]+a[i+1:]
print(max(a[i+1]-a[i] for i in range(n-2)))

n = int(input())
a = list(map(int, input().split()))
s = list()
for i in range(n-1):
    s.append(a[i+1] - a[i])
diff = max(s)
minsum = 10000
for i in range(0, len(s)-1):
    if s[i]+s[i+1] < minsum:
        minsum = s[i]+s[i+1]
if minsum > diff:
    print(minsum)
else:
    print(diff)

'''
Created on ١٧‏/١٢‏/٢٠١٤

@author: mohamed265
'''
input()
t = [int(x) for x in input().split()]
n = len(t) - 1
temp = 1000000000
for i in range(1, n):
    temp2 = 0
    for j in range(n):
        # if i + 1 == j:
        #     temp2 = max(temp2 , t[j + 2] - t[j])
        # el
        if j + 1 == i:
             temp2 = max(temp2 , t[j + 2] - t[j])
        elif i != j:
            temp2 = max(temp2 , t[j + 1] - t[j])
    temp = min(temp , temp2)
print(temp)


# A

n = int(input())
l = input().split()
ans = 10**50
for i in range(n):
    l[i] = int(l[i])
for i in range(1,n-1):
    curr = 0
    m = l[:i]+l[i+1:]
    for i in range(n-2):
        curr = max(curr,m[i+1]-m[i])
    if curr < ans:
        ans = curr
print(ans)


import sys
nu = int(sys.stdin.readline())
a=list(map(int,sys.stdin.readline().split()))
r=max(a)
for j in range(1,nu-1):
  x=0
  b=a[:]
  b.remove(a[j])
  for i in range(0,nu-2):
    x=max(x,b[i+1]-b[i])
  r=min(r,x)
  
print(r)

'''
Created on Dec 17, 2014

@author: Yehiaaa
'''
input()

x = [int (n) for n in input().split()]

t = len(x)-1
mi = 10000000000000

for i in range(1,t):
    mins = 0
    temp2 = 0
    for j in range(t):    
        if j+1 == i:
            mins = x[j+2] - x[j]
            
        elif i != j:
            mins = x[j+1] - x[j]
        temp2 = max(mins,temp2)
    mi = min(mi,temp2) 
print (mi)  
            
            


def dif(x):
    return max([b-a for b,a in zip(x[1:],x[:-1])])
def main(n,a):
    mn = dif(a)*10e10
    for i in range(1,len(a)-1):
        x = dif(a[:i]+a[i+1:])
        if x < mn: mn = x
        #print(i,x,mn)
    print(mn)


def main_input():
    n = int(input())
    a = [int(i) for i in input().split()]
    main(n,a)

def __starting_point():
    main_input()

__starting_point()

def main():
    n = int(input())
    rdl = input().split()
    scp = []
    for i in range(len(rdl)):
        scp.append(int(rdl[i]))
    mn = 10000000
    mx = 0
    maxs = []
    for i in range(len(scp)-1):
        if i != 0:
            mx = 0
            cur  = scp[:i] + scp[i+1:]
            for j in range(len(cur)-1):
                curt = cur[j+1] - cur[j]
                if curt > mx:
                    mx = curt
            maxs.append(mx)
    mn = 1000000
    for i in range(len(maxs)):
        if maxs[i] < mn:
            mn = maxs[i]
    print(mn)
main()


n = int(input())
a = list(map(int, input(). split()))
sl = []; s2 = []
for i in range(n - 2):
    sl += [a[i + 2] - a[i]]
    s2 += [a[i + 1] - a[i]]
s2 += [a[-1] - a[-2]]
print(max(min(sl), max(s2)))

n=int(input())
lis=input().split()
for i in range(n):
    lis[i]=int(lis[i])
def diff(a):
    m=a[1]-a[0]
    for i in range(1,len(a)-1):
        if a[i+1]-a[i]>m:
            m=a[i+1]-a[i]
    return m

lis2=[]
for i in range(1,n-1):
    lis2.append(diff(lis[:i]+lis[i+1:]))
print(min(lis2))
    
               


n = int(input())
a = list(map(int, input().split()))
d = []
for i in range(1, n-1):
    temp = a[:]
    temp.remove(temp[i])
    tempD = -1
    for x in range(1, len(temp)):
        tempD = max(tempD, temp[x]-temp[x-1])
    d.append(tempD)
d.sort()
print(d[0])


n = int(input())

seq = list(map(int, input().split()))

res = []
for i in range(1, n-1):
    res.append((abs(seq[i]-seq[i-1]), abs(seq[i]-seq[i+1])))

seq.pop(res.index(min(res)) + 1)

MAX = 0
for i in range(1, n-1):
    if abs(seq[i] - seq[i-1]) > MAX:
        MAX = abs(seq[i] - seq[i-1])

print(MAX)


def cek(arr):
    maxx=0
    for i in range(len(arr)-1):
        kurang=int(arr[i+1])-int(arr[i])
        if kurang>maxx:
            maxx=kurang
    return maxx
n=int(input())
arr=[0]*n
b=input().split(" ")
for i in range(n):
    arr[i]=int(b[i])
narr=len(arr)
ign=0
minn=9999
for i in range(narr-2):
    ign+=1
    kan=[]
    for j in range(narr):
        if j == ign:
            continue
        else:
            kan+=[arr[j]]
    hasil=cek(kan)
    if hasil<minn:
        minn=hasil
            
print(minn)


import sys
numberofrocks=int(sys.stdin.readline())
listofrocks=list(map(int,sys.stdin.readline().rstrip('\n').split()))
listofgaps=[listofrocks[1]-listofrocks[0]]
listofgapsafterremoving=[]
for index in range(1,numberofrocks-1):
    listofgaps.append(listofrocks[index+1]-listofrocks[index])
    listofgapsafterremoving.append(listofrocks[index+1]-listofrocks[index-1]) 
solution=max(max(listofgaps),min(listofgapsafterremoving))
print(solution)