Lauren has a chart of distinct projected prices for a house over the next several years.  She must buy the house in one year and sell it in another, and she must do so at a loss.  She wants to minimize her financial loss.  

Example 

$price=[20,15,8,2,12]$   

Her minimum loss is incurred by purchasing in year $2$ at $price[1]=15$ and reselling in year $5$ at $price[4]=12$.  Return $15-12=3$.  

Function Description  

Complete the minimumLoss function in the editor below.   

minimumLoss has the following parameter(s):  

int price[n]: home prices at each year  

Returns   

int: the minimum loss possible  

Input Format

The first line contains an integer $n$, the number of years of house data. 

The second line contains $n$ space-separated long integers that describe each $\textit{price[i]}$.

Constraints

$2\leq n\leq2\times10^5$
$1\leq price[i]\leq10^{16}$
All the prices are distinct. 
A valid answer exists.

Subtasks

$2\leq n\leq1000$ for $50\%$ of the maximum score. 

Sample Input 0
3
5 10 3

Sample Output 0
2

Explanation 0

Lauren buys the house in year $1$ at $price[0]=5$ and sells it in year $3$ at $price[2]=3$ for a minimal loss of $5-3=2$.

Sample Input 1
5
20 7 8 2 5

Sample Output 1
2

Explanation 1

Lauren buys the house in year $2$ at $price[1]=7$ and sells it in year $5$ at $price[4]=5$ for a minimal loss of $7-5=2$.

Source: hackerrank | Difficulty: MEDIUM
Tags: Complete search


Solutions:
n = int(input())
l = [int(item) for item in input().split()]
l2 = l.copy()
d = {}
for i in range(len(l)):
	d[l[i]] = i
l = sorted(l)
m = float('inf')
for i in range(len(l) - 1):
	if d[l[i + 1]] < d[l[i]]:
		m = min(m, l[i + 1] - l[i])
print(m)


n = int(input())
p = list(map(int, input().strip().split()))
arr = [(p[i], i) for i in range(n)]
arr.sort(reverse=True)
res = arr[0][0]
for i in range(n - 1):
	p1 = arr[i]
	p2 = arr[i + 1]
	if p1[0] > p2[0] and p1[1] < p2[1]:
		if p1[0] - p2[0] < res:
			res = p1[0] - p2[0]
print(res)


n = int(input())
data = sorted([(int(x), i) for (i, x) in enumerate(input().split())], key=lambda x: (-x[0], x[1]))
ans = 10 ** 20
for i in range(n - 1):
	if 0 < data[i][0] - data[i + 1][0] < ans and data[i][1] < data[i + 1][1]:
		ans = data[i][0] - data[i + 1][0]
print(ans)


n = int(input())
p = [int(prices_temp) for prices_temp in input().strip().split(' ')]
prices = []

def searchidx(st, ed, num):
	if st == ed:
		return st
	mid = int((st + ed) / 2)
	if prices[mid] < num:
		return searchidx(mid + 1, ed, num)
	else:
		return searchidx(st, mid, num)
ans = 10000000000000000
for i in range(n):
	idx = searchidx(0, i, p[i])
	prices.insert(idx, p[i])
	if idx < i:
		if prices[idx + 1] - prices[idx] < ans:
			ans = prices[idx + 1] - prices[idx]
print(ans)


import json
n = int(input().strip())
num = list(map(int, input().strip().split()))
data = [[i, num[i]] for i in range(n)]
data.sort(key=lambda tup: tup[1], reverse=True)
j = 0
minn = 10 ** 16
for i in range(n - 1):
	if data[i + 1][0] > data[i][0]:
		minn = min(minn, data[i][1] - data[i + 1][1])
print(minn)


n = int(input())
a = [int(i) for i in input().split()]
ind = sorted(range(len(a)), key=a.__getitem__, reverse=True)
a = sorted(a, reverse=True)
mindiff = 100000000
for i in range(n - 1):
	diff = a[i] - a[i + 1]
	if mindiff > diff and diff > 0 and (ind[i] - ind[i + 1] < 0):
		mindiff = diff
print(mindiff)


def minimalLoss():
	numberOfYears = int(input())
	housePrices = [int(price) for price in input().split(' ')]
	minimumDiff = -1
	priceTuples = []
	for i in range(0, numberOfYears):
		priceTuples.append((housePrices[i], i))
	sortedPrices = sorted(priceTuples, key=lambda price: price[0])
	for i in range(numberOfYears - 1, 0, -1):
		if minimumDiff == 1:
			return minimumDiff
		if minimumDiff < 0 and sortedPrices[i][1] < sortedPrices[i - 1][1]:
			minimumDiff = sortedPrices[i][0] - sortedPrices[i - 1][0]
		elif sortedPrices[i][1] < sortedPrices[i - 1][1] and sortedPrices[i][0] - sortedPrices[i - 1][0] < minimumDiff:
			minimumDiff = sortedPrices[i][0] - sortedPrices[i - 1][0]
	return minimumDiff
print(minimalLoss())


n = int(input())
v = [int(i) for i in input().split()]
x = 10000000000000000
v1 = sorted(v)
ind = {}
j = 0
prev = {v1[0]: -1}
for i in range(1, n):
	prev.update({v1[i]: v1[i - 1]})
for i in v1:
	ind.update({i: j})
	j = j + 1
for i in v:
	if prev[i] == -1:
		pass
	else:
		if x > i - prev[i]:
			x = i - prev[i]
		if ind[i] + 1 < n:
			prev[v1[ind[i] + 1]] = prev[i]
print(x)


import math
n = int(input())
a = input().split(' ')
a = list(map(int, a))
fin = math.pow(10, 16) + 1
b = {}
for i in range(0, n):
	b[a[i]] = i
a.sort()
for i in range(0, n - 1):
	temp = a[i + 1] - a[i]
	if b[a[i + 1]] < b[a[i]] and temp < fin:
		fin = temp
print(fin)


import sys
input()
data = []
i = 0
for d in input().strip().split():
	data.append((int(d), i))
	i += 1
data.sort()
minVal = sys.maxsize
for i in range(0, len(data) - 1):
	dif = data[i + 1][0] - data[i][0]
	pos = data[i][1] - data[i + 1][1]
	if dif < minVal and pos > 0:
		minVal = dif
print(minVal)


import bisect
import sys

def closest(sorted_list, number):
	pos = bisect.bisect_left(sorted_list, number)
	if pos == 0:
		return sorted_list[0]
	while sorted_list[pos] > number:
		pos -= 1
	return sorted_list[pos]
n = input()
prices = [int(x) for x in input().split()]
bisect_elements = [prices[-1]]
result = sys.maxsize
for i in range(len(prices) - 2, -1, -1):
	position = bisect.bisect_left(bisect_elements, prices[i])
	if position >= len(bisect_elements):
		bisect.insort(bisect_elements, prices[i])
		continue
	next_number = closest(bisect_elements, prices[i])
	net = prices[i] - next_number
	if net == 0:
		result = 0
		break
	elif net > 0 and net < result:
		result = net
	bisect.insort(bisect_elements, prices[i])
if result == sys.maxsize:
	result = -1
print(result)


n = int(input())
p = []
i = 0
for price in input().strip().split(' '):
	p.append((int(price), i))
	i += 1
p.sort(reverse=True)
min_diff = p[0][0] - p[1][0]
for i in range(n - 1):
	if p[i][0] - p[i + 1][0] < min_diff:
		if p[i][1] < p[i + 1][1]:
			min_diff = p[i][0] - p[i + 1][0]
print(min_diff)


n = int(input())
prices = [int(p) for p in input().strip().split(' ')]
import bisect

def get_min(l, p):
	position = bisect.bisect(l, p)
	return -1 if position >= len(l) else l[position - 1]
right_prices = [prices[-1]]
min_loss = prices[-1]
for i in range(len(prices) - 2, -1, -1):
	min_to_right = get_min(right_prices, prices[i])
	if min_to_right > 0:
		d = prices[i] - min_to_right
		diff = d if d >= 0 else prices[-1]
		min_loss = min(min_loss, diff)
	bisect.insort(right_prices, prices[i])
print(min_loss)


import sys
n = int(input().strip())
p = [int(p_i) for p_i in input().strip().split(' ')]
p_index = [(p[i], i) for i in range(n)]
p_sorted = sorted(p_index, key=lambda p_i: -p_i[0])
loss = max(p)
for i in range(n - 1):
	p_i = p_sorted[i]
	p_ii = p_sorted[i + 1]
	loss_i = p_i[0] - p_ii[0]
	if p_i[1] < p_ii[1] and loss > loss_i:
		loss = loss_i
print(loss)


n = int(input().strip())
p = [int(x) for x in input().strip().split()]
loss = max(p) - min(p)
xi = 0
d = []
b = p[:]
b.sort(reverse=True)

def funct(xi, b, n, d):
	while xi < n - 1:
		d.append(b[xi] - b[xi + 1])
		xi += 1
	e = d.index(min(d))
	x = b[e]
	y = b[e + 1]
	if p.index(x) < p.index(y):
		return x - y
	else:
		d[e] = max(d) + 1
		return funct(xi, b, n, d)
print(funct(xi, b, n, d))


import sys
from collections import OrderedDict
n = int(input())
minLose = sys.maxsize
prices = list(OrderedDict.fromkeys(input().strip().split(' ')))
prices = [int(p) for p in prices]
size = len(prices)
orgSeq = list(prices)
prices.sort()
for x in range(size - 1):
	if minLose > prices[x + 1] - prices[x] > 0:
		if orgSeq.index(prices[x + 1]) < orgSeq.index(prices[x]):
			minLose = prices[x + 1] - prices[x]
print(minLose)


n = int(input())
prices = list(map(int, input().strip().split()))
mymap = {}
for i in range(n):
	mymap[prices[i]] = i
prices.sort()
cur = prices[n - 1] - prices[0]
for i in range(n):
	idx = mymap[prices[i]]
	for j in range(i + 1, n):
		if prices[j] - prices[i] >= cur:
			break
		if mymap[prices[j]] < idx:
			cur = min(cur, prices[j] - prices[i])
			break
print(cur)


n = int(input())
arr = [int(t) for t in input().split(' ')]
arr1 = []
for i in range(n):
	arr1.append((arr[i], i))
arr1.sort()
j = 1
while True:
	mini = 10 ** 8
	for i in range(n - j):
		if arr1[i][1] > arr1[i + j][1]:
			mini = min(mini, arr1[i + 1][0] - arr1[i][0])
	if mini == 10 ** 8:
		j += 1
	else:
		break
print(mini)


n = int(input())
price = list(map(int, input().strip().split()))
temp = sorted(price)
ans = 10 ** 17
for i in range(1, n):
	n = temp[i] - temp[i - 1]
	if n < ans:
		if price.index(temp[i]) < price.index(temp[i - 1]):
			ans = n
print(ans)


n = int(input())
prices = list((int(x) for x in input().split()))
result = zip(prices, range(n))
answer = 10 ** 16
results = sorted(result)
for x in range(n - 1):
	if results[x][1] > results[x + 1][1]:
		if results[x + 1][0] - results[x][0] < answer:
			answer = results[x + 1][0] - results[x][0]
print(answer)


import itertools
n = int(input().strip())
prices = [int(price) for price in input().strip().split(' ')]
sorted_indexed_prices = sorted(((price, i) for (i, price) in enumerate(prices)))
min_loss = None
for (A, B) in zip(sorted_indexed_prices, sorted_indexed_prices[1:]):
	(a_price, a_year) = A
	(b_price, b_year) = B
	if a_year < b_year:
		continue
	loss = b_price - a_price
	if min_loss is None or loss < min_loss:
		min_loss = loss
print(min_loss)


import sys
n = int(input())
a = [int(x) for x in input().split()]
d = dict()
for i in range(len(a)):
	if a[i] not in d:
		d.update({a[i]: i})
a = list(set(a))
a.sort()
loss = sys.maxsize
for i in range(len(a) - 1):
	p = a[i]
	q = a[i + 1]
	if d[q] < d[p]:
		diff = q - p
		if diff < loss:
			loss = diff
print(loss)


import sys
years = int(input().strip().split(' ')[0])
prices = [int(prices_temp) for prices_temp in input().strip().split(' ')]
indexDict = dict()
for (index, price) in enumerate(prices):
	indexDict[price] = index
prices.sort()
for n in range(1, len(prices)):
	losses = [x - prices[i - n] for (i, x) in enumerate(prices) if i - n >= 0 and indexDict[x] < indexDict[prices[i - n]] and (x != prices[i - n])]
	if losses:
		print(min(losses))
		break


n = int(input())
a = list(map(int, input().split(' ')))
from bisect import bisect
min_diff = 10 ** 16
sorted_list = []
for x in reversed(a):
	i = bisect(sorted_list, x)
	if 0 < i < len(sorted_list):
		min_diff = min(min_diff, x - sorted_list[i - 1])
	sorted_list.insert(i, x)
print(min_diff)


year = {}
n = int(input().strip())
arr = [int(x) for x in input().strip().split(' ')]
for (i, item) in enumerate(arr):
	year[item] = i + 1
arr.sort()
ans = float('inf')
for i in range(n - 1):
	if year[arr[i + 1]] < year[arr[i]]:
		temp = arr[i + 1] - arr[i]
		if ans > temp:
			ans = temp
print(ans)


n = int(input())
xs = [int(x) for x in input().split(' ')]
i = 0
m = 2 ** 31 - 1
ys = [(x, i) for (i, x) in enumerate(xs)]
ys.sort()
while i < n - 1:
	(x, y) = ys[i]
	(x1, y1) = ys[i + 1]
	if y1 < y and x1 - x > 0 and (x1 - x < m):
		m = x1 - x
	i += 1
print(m)


(n, p) = (int(input()), list(map(int, input().split(' '))))
s = sorted(list(set(p)))
l = []
for i in range(1, len(s)):
	l.append(s[i] - s[i - 1])
c = 0
while c < len(s):
	a = l.index(max(0, min(l)))
	b = p.index(s[a])
	if s[a + 1] in p[:b]:
		print(l[a])
		break
	else:
		c += 1
		l[a] = 999999999


def solution():
	(n, p) = (int(input()), list(map(int, input().split(' '))))
	s = sorted(list(set(p)))
	l = []
	for i in range(1, len(s)):
		l.append(s[i] - s[i - 1])
	counter = 0
	while counter < len(s):
		a = l.index(min(l))
		b = p.index(s[a])
		if s[a + 1] in p[:b]:
			print(l[a])
			break
		else:
			counter += 1
			l[a] = max(l)
solution()


(n, p) = (int(input()), list(map(int, input().split(' '))))
s = sorted(list(set(p)))
l = []
for i in range(1, len(s)):
	l.append(s[i] - s[i - 1])
counter = 0
while counter < len(s):
	a = l.index(min(l))
	b = p.index(s[a])
	if s[a + 1] in p[:b]:
		print(l[a])
		break
	else:
		counter += 1
		l[a] = max(l)


import bisect
n = int(input())
prices = [int(i) for i in input().split(' ')]
min = -1
prev = list()
for p in prices:
	bisect.insort(prev, p)
	try:
		next = prev[bisect.bisect_right(prev, p)]
		if min == -1 or next - p < min:
			min = next - p
	except IndexError:
		pass
print(min)


n = int(input().strip())
numbers = list(map(int, input().strip().split()))
nums = list(numbers)
nums.sort()
minCost = sum(nums)
for i in range(1, n):
	if nums[i] - nums[i - 1] < minCost and numbers.index(nums[i]) < numbers.index(nums[i - 1]):
		minCost = nums[i] - nums[i - 1]
print(minCost)


from bisect import bisect
n = int(input())
p = list(map(int, input().strip().split()))
min_loss = 10 ** 16
a = [p[n - 1]]
for i in range(n - 2, -1, -1):
	cp = p[i]
	pos = bisect(a, cp)
	a.insert(pos, cp)
	if pos - 1 >= 0 and cp > a[pos - 1]:
		loss = cp - a[pos - 1]
		if loss < min_loss:
			min_loss = loss
	if pos + 1 < len(a) and cp > a[pos + 1]:
		loss = cp - a[pos + 1]
		if loss < min_loss:
			min_loss = loss
print(min_loss)


(n, p) = (int(input()), list(map(int, input().split(' '))))
s = sorted(list(set(p)))
l = []
for i in range(1, len(s)):
	l.append(s[i] - s[i - 1])
counter = 0
while counter < len(s):
	a = l.index(min(l))
	b = p.index(s[a])
	if s[a + 1] in p[:b]:
		print(l[a])
		break
	else:
		counter += 1
		l[a] = max(l)


class Node:
	__slots__ = ['data', 'left', 'right']

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

def insert(node, root):
	ins = False
	minimum = float('inf')
	while not ins:
		if node.data < root.data:
			if root.data - node.data < minimum:
				minimum = root.data - node.data
			if root.left:
				root = root.left
			else:
				root.left = node
				ins = True
		elif node.data > root.data:
			if root.right:
				root = root.right
			else:
				root.right = node
				ins = True
		else:
			ins = True
	return minimum
n = int(input().strip())
prices = list(map(int, input().strip().split(' ')))
root = Node(prices[0])
minimum_loss = float('inf')
for p in prices[1:]:
	loss = insert(Node(p), root)
	if loss < minimum_loss:
		minimum_loss = loss
print(minimum_loss)


n = int(input().strip())
numbers = list(map(int, input().strip().split()))
nums = list(numbers)
nums.sort()
minCost = sum(nums)
for i in range(1, n):
	if nums[i] - nums[i - 1] < minCost and numbers.index(nums[i]) < numbers.index(nums[i - 1]):
		minCost = nums[i] - nums[i - 1]
print(minCost)


n = int(input().strip())
numbers = list(map(int, input().strip().split()))
nums = list(numbers)
nums.sort()
minCost = sum(nums)
for i in range(1, n):
	if nums[i] - nums[i - 1] < minCost and numbers.index(nums[i]) < numbers.index(nums[i - 1]):
		minCost = nums[i] - nums[i - 1]
print(minCost)


from heapq import heappush, heappop
n = int(input())
p = [int(_) for _ in input().split(' ')]
heap = list()
for ii in range(n):
	heappush(heap, (p[ii], ii))
(prev_price, prev_year) = heappop(heap)
min_diff = 10 ** 17
while heap:
	(price, year) = heappop(heap)
	if year < prev_year and price - prev_price < min_diff:
		min_diff = price - prev_price
	(prev_price, prev_year) = (price, year)
print(min_diff)


n = int(input().strip())
numbers = list(map(int, input().strip().split()))
nums = list(numbers)
nums.sort()
minCost = sum(nums)
for i in range(1, n):
	if nums[i] - nums[i - 1] < minCost and numbers.index(nums[i]) < numbers.index(nums[i - 1]):
		minCost = nums[i] - nums[i - 1]
print(minCost)


n = int(input().strip())
numbers = list(map(int, input().strip().split()))
nums = list(numbers)
nums.sort()
minCost = sum(nums)
for i in range(1, n):
	if nums[i] - nums[i - 1] < minCost and numbers.index(nums[i]) < numbers.index(nums[i - 1]):
		minCost = nums[i] - nums[i - 1]
print(minCost)


n = int(input().strip())
a = [int(x) for x in input().strip().split(' ')]
r = -1
d = {}
for i in range(n):
	d[a[i]] = i
a.sort()
for i in range(n - 1):
	if d[a[i]] > d[a[i + 1]]:
		t = a[i + 1] - a[i]
		if r == -1 or r > t:
			r = t
print(r)


import math
n = int(input())
p = [int(i) for i in input().split(' ')]
p = [(p[i], i) for i in range(n)]
p.sort()
ans = math.inf
for i in range(1, n):
	if p[i][0] - p[i - 1][0] < ans and p[i][1] < p[i - 1][1]:
		ans = p[i][0] - p[i - 1][0]
print(ans)


N = int(input())
prices = list(map(int, input().split()))
indexedPrices = sorted(enumerate(prices), key=lambda tuple: tuple[1], reverse=True)
maxPrice = indexedPrices[0]
diff = []
for price in indexedPrices:
	if maxPrice[0] < price[0]:
		diff.append(maxPrice[1] - price[1])
	maxPrice = price
print(min(diff))


n = int(input().strip())
arr = [(i, int(s)) for (i, s) in enumerate(input().strip().split())]
arr = sorted(arr, key=lambda x: x[1])
minDiff = (arr[-1][1] - arr[0][1]) * 2
for i in range(len(arr) - 1):
	diff = arr[i + 1][1] - arr[i][1]
	if diff < minDiff:
		if arr[i + 1][0] < arr[i][0]:
			minDiff = diff
print(minDiff)


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

def solve(n, prices):
	ps = list(sorted(prices))
	diffs = [p - ps[i] for (i, p) in enumerate(ps[1:])]
	for _ in range(len(diffs) + 1):
		smallest_diff_index = diffs.index(min(diffs))
		price_index = prices.index(ps[smallest_diff_index])
		if ps[smallest_diff_index + 1] in prices[:price_index]:
			return diffs[smallest_diff_index]
		else:
			diffs[smallest_diff_index] = max(diffs)
print(solve(n, prices))


import math
N = int(input())
prices = list([int(x) for x in input().split(' ')])
prices = sorted(enumerate(prices), key=lambda x: x[1], reverse=True)
minimum_loss = math.pow(10, 16)
for i in range(N):
	(year, price) = prices[i]
	j = i + 1
	while j < N and prices[j][0] < year:
		j += 1
	if j < N:
		minimum_loss = min(minimum_loss, prices[i][1] - prices[j][1])
print(minimum_loss)


n = int(input())
a = list(map(int, input().strip().split()))
d = {}
for i in range(n):
	d[a[i]] = i
a.sort()
minim = a[n - 1]
for i in range(1, n):
	if a[i] - a[i - 1] < minim and d[a[i]] < d[a[i - 1]]:
		minim = a[i] - a[i - 1]
print(minim)


n = int(input())
l = input().split(' ')
l = [int(i) for i in l]
dic = {}
for i in range(len(l)):
	dic[l[i]] = i
l = sorted(l)
mini = 1000000
for i in range(len(l) - 1):
	diff = l[i + 1] - l[i]
	if dic[l[i + 1]] < dic[l[i]] and diff > 0:
		if diff < mini:
			mini = diff
print(mini)


n = int(input())
l = list(map(int, input().split()))
d = {}
ans = 10 ** 16
for i in range(n):
	d[l[i]] = i
l = sorted(l)
ans = l[1] - l[0]
for i in range(n - 1):
	if d[l[i]] > d[l[i + 1]]:
		ans = min(ans, l[i + 1] - l[i])
print(ans)


n = int(input().strip())
numbers = list(map(int, input().strip().split()))
nums = list(numbers)
nums.sort()
minCost = sum(nums)
for i in range(1, n):
	if nums[i] - nums[i - 1] < minCost and numbers.index(nums[i]) < numbers.index(nums[i - 1]):
		minCost = nums[i] - nums[i - 1]
print(minCost)


n = int(input())
a = list(map(int, input().split()))
r = list(range(0, n))
z = sorted(zip(a, r))
m = 10 ** 16
for i in range(0, n - 1):
	if z[i][1] > z[i + 1][1]:
		m = min(z[i + 1][0] - z[i][0], m)
print(m)


import sys
N = int(sys.stdin.readline())
arr = [int(elem) for elem in sys.stdin.readline().split()]
d = {}
for i in range(len(arr)):
	d[arr[i]] = i
result = 2 ** 32
arr.sort()
for i in range(len(arr) - 1):
	for k in range(i + 1, len(arr)):
		if arr[k] - arr[i] > result:
			break
		if d[arr[k]] < d[arr[i]] and arr[k] - arr[i] < result:
			result = arr[k] - arr[i]
			break
print(result)


n = int(input().strip())
numbers = list(map(int, input().strip().split()))
nums = list(numbers)
nums.sort()
minCost = sum(nums)
for i in range(1, n):
	if nums[i] - nums[i - 1] < minCost and numbers.index(nums[i]) < numbers.index(nums[i - 1]):
		minCost = nums[i] - nums[i - 1]
print(minCost)


n = int(input())
prices = [int(x) for x in input().split()]
copy = prices[:]
min_loss = float('inf')
copy.sort()
for i in range(n - 1):
	loss = copy[i + 1] - copy[i]
	if loss < min_loss and prices.index(copy[i + 1]) < prices.index(copy[i]):
		min_loss = loss
print(min_loss)


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

class house:

	def __init__(self, year, price):
		self.year = year
		self.price = price
houses = []
for i in range(n):
	temp = house(i, prices[i])
	houses.append(temp)
houses.sort(key=lambda house: house.price)
loss = houses[-1].price
for i in range(n - 1):
	temp = houses[i + 1].price - houses[i].price
	if temp < loss and houses[i].year > houses[i + 1].year:
		loss = temp
print(loss)


import bisect
n = int(input())
str = input().split()
a = [int(str[0])]
res = 10 ** 16
for i in range(1, n, 1):
	p = int(str[i])
	index = bisect.bisect_left(a, p)
	a.insert(index, p)
	if index + 1 < len(a):
		res = min(res, a[index + 1] - a[index])
print(res)


n = int(input())
num = list(map(int, input().strip().split()))
arr = list(num)
arr.sort()
maxu = 2 * arr[n - 1]
for i in range(1, n):
	if arr[i] - arr[i - 1] < maxu and num.index(arr[i]) < num.index(arr[i - 1]):
		maxu = arr[i] - arr[i - 1]
print(maxu)


(n, p) = (int(input()), list(map(int, input().split(' '))))
s = sorted(list(set(p)))
l = []
for i in range(1, len(s)):
	l.append(s[i] - s[i - 1])
counter = 0
while counter < len(s):
	a = l.index(min(l))
	b = p.index(s[a])
	if s[a + 1] in p[:b]:
		print(l[a])
		break
	else:
		counter += 1
		l[a] = max(l)


n = int(input().strip())
numbers = list(map(int, input().strip().split()))
nums = list(numbers)
nums.sort()
minCost = sum(nums)
for i in range(1, n):
	if nums[i] - nums[i - 1] < minCost and numbers.index(nums[i]) < numbers.index(nums[i - 1]):
		minCost = nums[i] - nums[i - 1]
print(minCost)


price_num = int(input())
price_temp = [int(x) for x in input().split(' ')]
prices = [(y, x) for (x, y) in enumerate(price_temp)]
prices.sort()
min_diff = float('Inf')
for x in range(price_num - 1):
	price_datum1 = prices[x]
	price_datum2 = prices[x + 1]
	if price_datum2[1] > price_datum1[1]:
		continue
	if price_datum2[0] == price_datum1[0]:
		continue
	diff = price_datum2[0] - price_datum1[0]
	if diff < min_diff:
		min_diff = diff
print(min_diff)


n = int(input().strip())
numbers = list(map(int, input().strip().split()))
nums = list(numbers)
nums.sort()
minCost = sum(nums)
for i in range(1, n):
	if nums[i] - nums[i - 1] < minCost and numbers.index(nums[i]) < numbers.index(nums[i - 1]):
		minCost = nums[i] - nums[i - 1]
print(minCost)


n = int(input().strip())
numbers = list(map(int, input().strip().split()))
nums = list(numbers)
nums.sort()
minCost = sum(nums)
for i in range(1, n):
	if nums[i] - nums[i - 1] < minCost and numbers.index(nums[i]) < numbers.index(nums[i - 1]):
		minCost = nums[i] - nums[i - 1]
print(minCost)


n = int(input().strip())
year = [int(a) for a in input().strip().split(' ')]
nums = list(year)
nums = sorted(nums)
minCost = sum(nums)
for i in range(1, n):
	if nums[i] - nums[i - 1] < minCost and year.index(nums[i]) < year.index(nums[i - 1]):
		minCost = nums[i] - nums[i - 1]
print(minCost)


n = int(input())
p = map(int, input().split())
pricepos = [(price, pos) for (pos, price) in enumerate(p)]
pricepos.sort()
diffs = []
for ix in range(len(pricepos) - 1):
	(price1, pos1) = pricepos[ix]
	(price2, pos2) = pricepos[ix + 1]
	if pos1 > pos2:
		(price1, price2) = (price2, price1)
	if price1 > price2:
		diff = price1 - price2
		diffs.append(diff)
print(min(diffs))


import sys
n = int(input().strip())
arr = input().strip()
arr = list(map(int, arr.split(' ')))
d = {}
for i in range(1, n + 1):
	d[arr[i - 1]] = i
arr.sort(reverse=True)
min_loss = sys.maxsize
for i in range(n - 1):
	diff = arr[i] - arr[i + 1]
	if d[arr[i]] < d[arr[i + 1]] and diff < min_loss:
		min_loss = diff
print(min_loss)


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

def insert(p, trees):
	insertion_children = None
	best = float('inf')
	for (key, children) in trees:
		if 0 < key - p < best:
			best = key - p
			insertion_children = children
	if insertion_children is not None:
		insert(p, insertion_children)
	else:
		trees.append((p, []))

def find_best_diff(tree):
	best_diff = float('inf')
	for child in tree[1]:
		best_diff = min(best_diff, tree[0] - child[0], find_best_diff(child))
	return best_diff

def solve(ps):
	trees = []
	for p in ps:
		insert(p, trees)
	best_diff = min((find_best_diff(tree) for tree in trees))
	return best_diff
print(solve(ps))


(size, array, d, ans) = (int(input()), list(map(int, input().split())), {}, 10 ** 16)
for i in range(size):
	d[array[i]] = i
array.sort()
for i in range(size - 1):
	if array[i] != array[i + 1] and d[array[i]] > d[array[i + 1]]:
		ans = min(ans, array[i + 1] - array[i])
print(ans)


n = int(input().strip())
numbers = list(map(int, input().strip().split()))
nums = list(numbers)
nums.sort()
minCost = sum(nums)
for i in range(1, n):
	if nums[i] - nums[i - 1] < minCost and numbers.index(nums[i]) < numbers.index(nums[i - 1]):
		minCost = nums[i] - nums[i - 1]
print(minCost)


n = int(input())
a = input().split()
a = [int(x) for x in a]
x = sorted(a)
b = []
for i in range(n - 1):
	b.append([x[i + 1] - x[i], x[i]])
b.sort()
i = 0
while True:
	if a.index(b[i][1]) > a.index(b[i][0] + b[i][1]):
		print(b[i][0])
		break
	i += 1


import bisect
n = int(input().strip())
p = [int(x) for x in input().strip().split()]
ps = []
minloss = 10 ** 16
for i in range(n):
	pp = p[n - 1 - i]
	a = bisect.bisect_left(ps, pp)
	if a > 0:
		loss = pp - ps[a - 1]
		if loss < minloss:
			minloss = loss
	bisect.insort(ps, pp)
print(minloss)


import sys
n = int(input())
prices = [int(x) for x in input().strip().split(' ')]
places = {}
for i in range(len(prices)):
	places[prices[i]] = i
prices.sort()
losses = []
for i in range(1, len(prices)):
	loss = prices[i] - prices[i - 1]
	time = places[prices[i - 1]] - places[prices[i]]
	if time > 1 and loss > 0:
		losses.append(loss)
min_loss = min(losses)
print(min_loss)


n = int(input().strip())
numbers = list(map(int, input().strip().split()))
nums = list(numbers)
nums.sort()
minCost = sum(nums)
for i in range(1, n):
	if nums[i] - nums[i - 1] < minCost and numbers.index(nums[i]) < numbers.index(nums[i - 1]):
		minCost = nums[i] - nums[i - 1]
print(minCost)


n = int(input().strip())
numbers = list(map(int, input().strip().split()))
nums = list(numbers)
nums.sort()
minCost = sum(nums)
for i in range(1, n):
	if nums[i] - nums[i - 1] < minCost and numbers.index(nums[i]) < numbers.index(nums[i - 1]):
		minCost = nums[i] - nums[i - 1]
print(minCost)


n = int(input().strip())
numbers = list(map(int, input().strip().split()))
nums = list(numbers)
nums.sort()
minCost = sum(nums)
for i in range(1, n):
	if nums[i] - nums[i - 1] < minCost and numbers.index(nums[i]) < numbers.index(nums[i - 1]):
		minCost = nums[i] - nums[i - 1]
print(minCost)


n = int(input())
temp = list(map(int, input().split(' ')))
temp2 = sorted(enumerate(temp), key=lambda x: x[1])
temp = sorted(temp)
smallest = 1000000
for i in range(n - 1):
	t = temp[i + 1] - temp[i]
	if t < smallest:
		if temp2[i + 1][0] < temp2[i][0]:
			smallest = t
print(smallest)


n = int(input().strip())
numbers = list(map(int, input().strip().split()))
nums = list(numbers)
nums.sort()
minCost = sum(nums)
for i in range(1, n):
	if nums[i] - nums[i - 1] < minCost and numbers.index(nums[i]) < numbers.index(nums[i - 1]):
		minCost = nums[i] - nums[i - 1]
print(minCost)


from math import inf

class Node(object):

	def __init__(self, key, left=None, right=None):
		self.key = key
		self.left = left
		self.right = right

	def __repr__(self):
		return 'key: {}'.format(self.key)

	def __str__(self):
		return self.__repr__()

def insert(curr, node, succ):
	if curr.key >= node.key:
		if curr.left is None:
			curr.left = node
			return curr
		else:
			return insert(curr.left, node, curr)
	elif curr.right is None:
		curr.right = node
		return succ
	else:
		return insert(curr.right, node, succ)

def inorder_traversal(node, f):
	if node is None:
		return
	inorder_traversal(node.left, f)
	f(node)
	inorder_traversal(node.right, f)
	return

def main():
	n = int(input())
	arr = list(map(lambda x: int(x), input().split()))
	root = Node(arr[0])
	min_diff = inf
	for elem in arr[1:]:
		new_node = Node(elem)
		succ = insert(root, new_node, None)
		if succ is not None and succ.key - new_node.key < min_diff:
			min_diff = succ.key - new_node.key
	print(min_diff)
main()


class Node:

	def __init__(self, data, left, right):
		self.data = data
		self.left = left
		self.right = right

class BTree:

	def __init__(self):
		self.root = None

	def insert(self, data):
		self.root = self._insert(data, self.root)

	def _insert(self, data, node):
		if node is None:
			return Node(data, None, None)
		if data < node.data:
			node.left = self._insert(data, node.left)
		if node.data < data:
			node.right = self._insert(data, node.right)
		return node

	def ceiling(self, data):
		return self._ceiling(data, self.root)

	def _ceiling(self, data, node):
		if node is None:
			return None
		if node.data == data:
			return data
		if node.data < data:
			return self._ceiling(data, node.right)
		result = self._ceiling(data, node.left)
		if result is not None:
			return result
		return node.data
input()
l = [int(x) for x in input().split()]
min_so_far = float('infinity')
nums_so_far = BTree()
for x in l:
	ceiling = nums_so_far.ceiling(x)
	if ceiling is not None:
		loss = ceiling - x
		if loss > 0 and loss < min_so_far:
			min_so_far = loss
	nums_so_far.insert(x)
print(min_so_far)


import sys
(n, p) = (int(input()), list(map(int, input().split(' '))))
s = sorted(list(set(p)))
l = []
for i in range(1, len(s)):
	l.append(s[i] - s[i - 1])
counter = 0
while counter < len(s):
	a = l.index(min(l))
	b = p.index(s[a])
	if s[a + 1] in p[:b]:
		print(l[a])
		break
	else:
		counter += 1
		l[a] = max(l)


import operator
n = int(input())
house_price = [int(a) for a in input().strip().split(' ')]
dict_house_price = {}
for i in range(n):
	dict_house_price[i] = house_price[i]
dict_house_price = sorted(dict_house_price.items(), key=operator.itemgetter(1))
min = dict_house_price[n - 1][1]
for j in range(n - 1):
	if dict_house_price[j][0] > dict_house_price[j + 1][0] and min > dict_house_price[j + 1][1] - dict_house_price[j][1]:
		min = dict_house_price[j + 1][1] - dict_house_price[j][1]
print(min)


n = int(input().strip())
numbers = list(map(int, input().strip().split()))
nums = list(numbers)
nums.sort()
minCost = sum(nums)
for i in range(1, n):
	if nums[i] - nums[i - 1] < minCost and numbers.index(nums[i]) < numbers.index(nums[i - 1]):
		minCost = nums[i] - nums[i - 1]
print(minCost)


n = int(input())
arr = [int(a) for a in input().split()]
mini = 10000000000000000
sorted_array = sorted(arr)
i = 0
j = 1
while j < n:
	diff = sorted_array[j] - sorted_array[i]
	if diff < mini and arr.index(sorted_array[i]) > arr.index(sorted_array[j]):
		mini = diff
	i += 1
	j += 1
print(mini)


N = int(input().strip())
prices = [(i, int(p)) for (i, p) in enumerate(input().strip().split())]
less_loss = None

def part(start, end, prices):
	pivot = prices[end][1]
	j = end - 1
	i = start
	while True:
		while j >= 0 and prices[j][1] > pivot:
			j -= 1
		while i < end and prices[i][1] < pivot:
			i += 1
		if j < i:
			(prices[end], prices[i]) = (prices[i], prices[end])
			break
		(prices[j], prices[i]) = (prices[i], prices[j])
		i += 1
		j -= 1
	return i

def quick_sort(array, left, right):
	if right - left < 1:
		return
	if right - left == 1:
		if array[left][1] > array[right][1]:
			(array[left], array[right]) = (array[right], array[left])
			return
	p = part(left, right, array)
	quick_sort(array, left, p - 1)
	quick_sort(array, p + 1, right)
quick_sort(prices, 0, N - 1)
for index in range(1, N):
	if prices[index][0] < prices[index - 1][0] and prices[index][1] > prices[index - 1][1]:
		if less_loss is None or prices[index][1] - prices[index - 1][1] < less_loss:
			less_loss = prices[index][1] - prices[index - 1][1]
print(less_loss)


n = int(input())
ar = sorted(zip(map(int, input().split()), range(n)))
mloss = ar[-1][0] - ar[0][0]
for ((x0, p0), (x1, p1)) in zip(ar, ar[1:]):
	if x1 - x0 < mloss and p0 > p1:
		mloss = x1 - x0
print(mloss)


n = int(input().strip())
numbers = list(map(int, input().strip().split()))
nums = list(numbers)
nums.sort()
minCost = sum(nums)
for i in range(1, n):
	if nums[i] - nums[i - 1] < minCost and numbers.index(nums[i]) < numbers.index(nums[i - 1]):
		minCost = nums[i] - nums[i - 1]
print(minCost)


import math
m = math.inf
n = int(input())
p = [int(i) for i in input().split()]
d = {}
for i in range(n):
	d[i] = p[i]
a = sorted(d, key=d.get, reverse=True)
for i in range(n - 1):
	if a[i + 1] > a[i]:
		t = p[a[i]] - p[a[i + 1]]
		if t < m:
			m = t
print(m)


n = int(input().strip())
numbers = list(map(int, input().strip().split()))
nums = list(numbers)
nums.sort()
minCost = sum(nums)
for i in range(1, n):
	if nums[i] - nums[i - 1] < minCost and numbers.index(nums[i]) < numbers.index(nums[i - 1]):
		minCost = nums[i] - nums[i - 1]
print(minCost)


n = int(input())
lst = list(map(int, input().split()))
prefix = [(i, j) for (i, j) in enumerate(lst)]
prefix.sort(key=lambda x: x[1])
minloss = 10000000000
start = prefix[0]
for i in prefix[1:]:
	if start[0] > i[0]:
		loss = i[1] - start[1]
		if loss < minloss:
			minloss = loss
	start = i
print(minloss)


n = int(input().strip())
numbers = list(map(int, input().strip().split()))
nums = list(numbers)
nums.sort()
minCost = sum(nums)
for i in range(1, n):
	if nums[i] - nums[i - 1] < minCost and numbers.index(nums[i]) < numbers.index(nums[i - 1]):
		minCost = nums[i] - nums[i - 1]
print(minCost)


n = int(input())
p = list(map(int, input().strip().split()))
arr = [(p[i], i) for i in range(n)]
arr.sort(reverse=True)
res = arr[0][0]
for i in range(n - 1):
	p1 = arr[i]
	p2 = arr[i + 1]
	if p1[0] > p2[0] and p1[1] < p2[1]:
		if p1[0] - p2[0] < res:
			res = p1[0] - p2[0]
print(res)


n = int(input())
nums = list(map(int, input().strip().split()))
numbers = list(nums)
numbers.sort()
minimo = sum(numbers)
for i in range(n - 1):
	if numbers[i + 1] - numbers[i] < minimo and nums.index(numbers[i + 1]) < nums.index(numbers[i]):
		minimo = numbers[i + 1] - numbers[i]
print(minimo)


L = int(input())
prices = list(map(int, input().strip().split()))
temp = list(prices)
temp.sort()
loss = 2 ** 31 - 1
for i in range(0, L - 1):
	buy = temp[i + 1]
	sell = temp[i]
	if buy - sell < loss and prices.index(buy) < prices.index(sell):
		loss = buy - sell
print(loss)


import sys

class Node:

	def __init__(self, key):
		self.key = key
		self.left = None
		self.right = None

def findPreSuc(root, key):
	if root is None:
		return
	if root.key == key:
		if root.left is not None:
			tmp = root.left
			while tmp.right:
				tmp = tmp.right
			findPreSuc.pre = tmp
		if root.right is not None:
			tmp = root.right
			while temp.left:
				tmp = tmp.left
			findPreSuc.suc = tmp
		return
	if root.key > key:
		findPreSuc.suc = root
		findPreSuc(root.left, key)
	else:
		findPreSuc.pre = root
		findPreSuc(root.right, key)

def insert(node, key):
	if node is None:
		return Node(key)
	if key < node.key:
		node.left = insert(node.left, key)
	else:
		node.right = insert(node.right, key)
	return node
n = int(input().strip())
P = [int(p) for p in input().strip().split()]
root = None
min_loss = sys.maxsize
for p in P:
	findPreSuc.suc = None
	findPreSuc(root, p)
	if findPreSuc.suc is not None:
		next_larger = findPreSuc.suc.key
		min_loss = min(min_loss, next_larger - p)
	if root is None:
		root = insert(root, p)
	else:
		insert(root, p)
print(min_loss)


n = int(input())
p = [int(p_i) for p_i in input().split()]
indexes = dict(((p_i, i) for (i, p_i) in enumerate(p)))
p.sort()
min_loss = 10 ** 16
for i in range(len(p) - 1):
	loss = p[i + 1] - p[i]
	if loss < min_loss and indexes[p[i + 1]] < indexes[p[i]]:
		min_loss = loss
print(min_loss)


n = int(input())
P = [int(p) for p in input().split()]
ordered = dict(zip(P, list(range(n))))
min_ = 999999999999
P.sort()
for i in range(n - 1):
	cur = P[i + 1] - P[i]
	if cur < min_ and ordered[P[i + 1]] < ordered[P[i]]:
		min_ = cur
print(min_)


n = int(input())
p = [int(x) for x in input().split(' ')]
original = p[:]
p.sort()
items = []
min_value = float('inf')
for x in range(0, n - 1):
	value = p[x + 1] - p[x]
	if value < min_value and original.index(p[x + 1]) < original.index(p[x]):
		items.append(value)
		min_value = value
print(min(items))


n = int(input())
arr = list(map(int, input().split(' ')))
arr1 = list(arr)
arr.sort()
i = 0
min_ = 1000000000000000000
while i < len(arr) - 1:
	x = arr[i + 1] - arr[i]
	if x < min_ and arr1.index(arr[i]) > arr1.index(arr[i + 1]):
		min_ = x
	i += 1
print(min_)


n = int(input())
arr = list(map(int, input().split()))
di = {arr[i]: i for i in range(n)}
arr = sorted(arr)
m = 10000000
for i in range(1, n):
	if di[arr[i]] < di[arr[i - 1]]:
		m = min(m, arr[i] - arr[i - 1])
print(m)


no_of_years = input()
prices = list(map(int, input().split(' ')))
price_dict = dict(((price, index) for (index, price) in enumerate(prices)))
prices = sorted(prices)
maxdiff = prices[0] - prices[-1]
for i in range(len(prices) - 1):
	if prices[i] - prices[i + 1] > maxdiff and price_dict[prices[i + 1]] < price_dict[prices[i]]:
		maxdiff = prices[i] - prices[i + 1]
print(abs(maxdiff))


def fun(x):
	return x[-1]
n = int(input().strip())
a = [int(a_temp) for a_temp in input().strip().split()]
alist = []
for i in range(n):
	alist.append((i, a[i]))
alist = sorted(alist, key=fun)
diff = []
for i in range(n - 1):
	if alist[i][0] > alist[i + 1][0]:
		diff.append(alist[i + 1][1] - alist[i][1])
print(min(diff))


d = []
n = int(input())
b = []
b = input().split(' ')
b = [int(x) for x in b]
for i in range(len(b)):
	d.append((b[i], i + 1))

def val(x):
	return x[0]
d.sort(key=val, reverse=True)
mn = 1000000000000
for i in range(n - 1):
	if d[i][1] < d[i + 1][1]:
		s = d[i][0] - d[i + 1][0]
		if s < mn:
			mn = s
print(mn)