Given an unsorted array Arr[] of N integers and an integer X, find floor and ceiling of X in Arr[0..N-1].
Floor of X is the largest element which is smaller than or equal to X. Floor of X doesn’t exist if X is smaller than smallest element of Arr[].
Ceil of X is the smallest element which is greater than or equal to X. Ceil of X doesn’t exist if X is greater than greatest element of Arr[].
Example 1:
Input:
N = 8, X = 7
Arr[] = {5, 6, 8, 9, 6, 5, 5, 6}
Output: 6 8
Explanation:
Floor of 7 is 6 and ceil of 7 
is 8.
Example 2:
Input:
N = 8, X = 10
Arr[] = {5, 6, 8, 9, 6, 5, 5, 6}
Output: 9 -1
Explanation:
Floor of 10 is 9 but ceil of 10 is not 
possible.
Your Task:
You don't need to read input or print anything. Your task is to complete the function getFloorAndCeil() which takes the array of integers arr, n and x as parameters and returns a pair of integers denoting the answer. Return -1 if floor or ceil is not present.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints :
1 ≤ N ≤ 10^{5}
1 ≤ Arr[i], X ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3




def getFloorAndCeil(arr, n, x):
    # code here

Solutions:
def getFloorAndCeil(arr, n, x):
	floor = sorted([num for num in arr if num <= x])
	ceil = sorted([num for num in arr if num >= x])
	if floor == []:
		return [-1, ceil[0]]
	elif ceil == []:
		return [floor[-1], -1]
	elif floor == [] and ceil == []:
		return [-1, -1]
	else:
		return [floor[-1], ceil[0]]


def getFloorAndCeil(arr, n, x):
	arr = sorted(arr)
	op = [-1, -1]
	start = 0
	end = n - 1
	while start <= end:
		mid = (start + end) // 2
		if arr[mid] == x:
			op = [x, x]
			return op
		elif arr[mid] > x:
			op[1] = arr[mid]
			end = mid - 1
		elif arr[mid] < x:
			op[0] = arr[mid]
			start = mid + 1
	return op


import numpy as np

def getFloorAndCeil(arr, n, x):
	(maxi_floor, mini_ceil) = (-1, np.inf)
	for i in range(n):
		if arr[i] > maxi_floor and arr[i] <= x:
			maxi_floor = arr[i]
		if arr[i] >= x and arr[i] < mini_ceil:
			mini_ceil = arr[i]
	if mini_ceil == np.inf:
		return (maxi_floor, -1)
	else:
		return (maxi_floor, mini_ceil)


def getFloorAndCeil(arr, n, x):
	arr.sort()

	def findFloor(A, N, X):
		left = 0
		right = N - 1
		res = -1
		while left <= right:
			mid = (left + right) // 2
			if A[mid] <= X:
				res = mid
				left = mid + 1
			else:
				right = mid - 1
		return res

	def findCeil(A, N, X):
		left = 0
		right = N - 1
		res = -1
		while left <= right:
			mid = (left + right) // 2
			if A[mid] < X:
				left = mid + 1
			else:
				res = mid
				right = mid - 1
		return res
	return [arr[findFloor(arr, n, x)] if findFloor(arr, n, x) != -1 else -1, arr[findCeil(arr, n, x)] if findCeil(arr, n, x) != -1 else -1]


def getFloorAndCeil(arr, n, x):
	min_so_far = float('-inf')
	max_so_far = float('inf')
	for num in arr:
		if num < x:
			min_so_far = max(min_so_far, num)
		elif num > x:
			max_so_far = min(max_so_far, num)
		elif num == x:
			return (num, num)
	if min_so_far == float('-inf'):
		min_so_far = -1
	elif max_so_far == float('inf'):
		max_so_far = -1
	return (min_so_far, max_so_far)


def getFloorAndCeil(arr, n, x):
	flo = -1
	cei = float('inf')
	f = 1
	for i in arr:
		if i >= x and i < cei:
			f = 0
			cei = i
		if i <= x and i > flo:
			flo = i
	if f:
		cei = -1
	return (flo, cei)


def getFloorAndCeil(arr, n, x):
	floor = -1
	ceil = 10 ** 6 + 1
	for i in arr:
		if i <= x and floor < i:
			floor = i
		if i >= x and ceil > i:
			ceil = i
	if ceil == 10 ** 6 + 1:
		ceil = -1
	return [floor, ceil]


def getFloorAndCeil(arr, n, x):
	floor = -1
	ceil = float('inf')
	for i in arr:
		if i > floor and i <= x:
			floor = i
		if i < ceil and i >= x:
			ceil = i
	if ceil == float('inf'):
		ceil = -1
	return (floor, ceil)


def getFloorAndCeil(arr, n, x):
	arr.sort()
	l = 0
	r = n - 1
	res = [-1] * 2
	mid = 0
	while l <= r:
		mid = (l + r) // 2
		if arr[mid] == x:
			res[0] = arr[mid]
			res[1] = arr[mid]
			return res
		elif arr[mid] > x:
			r = mid - 1
			res[1] = arr[mid]
		elif arr[mid] < x:
			l = mid + 1
			res[0] = arr[mid]
	return res


def getFloorAndCeil(arr, n, x):
	floor = -1000000
	ceil = 1000000
	for i in range(n):
		if arr[i] <= x:
			if arr[i] >= floor:
				floor = arr[i]
		if arr[i] >= x:
			if arr[i] <= ceil:
				ceil = arr[i]
	if floor == -1000000:
		return (-1, ceil)
	elif ceil == 1000000:
		return (floor, -1)
	else:
		return (floor, ceil)


def getFloorAndCeil(arr, n, x):
	arr.sort()
	(floor, ceil) = (-1, -1)
	if x < arr[0]:
		ceil = arr[0]
		return (floor, ceil)
	if x > arr[n - 1]:
		floor = arr[n - 1]
		return (floor, ceil)
	for i in range(n):
		if arr[i] == x:
			floor = arr[i]
			ceil = arr[i]
			return (floor, ceil)
		if arr[i] < x:
			floor = arr[i]
		if arr[i] > x:
			ceil = arr[i]
			return (floor, ceil)
	return (floor, ceil)


def getFloorAndCeil(arr, n, x):
	low = 0
	high = n - 1
	arr.sort()
	floor = -1
	ceil = -1
	while low <= high:
		mid = (low + high) // 2
		if arr[mid] == x:
			ceil = arr[mid]
			floor = arr[mid]
			break
		elif arr[mid] < x:
			low = mid + 1
			floor = arr[mid]
		else:
			high = mid - 1
			ceil = arr[mid]
	return (floor, ceil)


def getFloorAndCeil(arr, n, x):
	(f, c) = (-1, -1)
	for y in arr:
		if y == x:
			(f, c) = (x, x)
			break
		if y > x and (c == -1 or y < c):
			c = y
		if y < x and (f == -1 or y > f):
			f = y
	return [f, c]


def getFloorAndCeil(arr, n, x):
	(l, r) = (0, n)
	arr.sort()
	while l < r:
		mid = l + (r - l) // 2
		if arr[mid] >= x:
			r = mid
		else:
			l = mid + 1
	ceil = arr[l] if l != n else -1
	(l, r) = (-1, n - 1)
	arr.sort()
	while l < r:
		mid = l + (r - l + 1) // 2
		if arr[mid] <= x:
			l = mid
		else:
			r = mid - 1
	floor = arr[l] if l != -1 else -1
	return [floor, ceil]


def getFloorAndCeil(arr, n, x):
	floor = -1
	ceil = -1
	for i in sorted(arr):
		if i <= x:
			floor = i
		if ceil == -1 and i >= x:
			ceil = i
	return [floor, ceil]


def getFloorAndCeil(arr, n, x):
	f = -1
	c = -1
	for i in range(n):
		if arr[i] == x:
			f = c = x
			break
		elif arr[i] < x:
			if arr[i] > f:
				f = arr[i]
		elif arr[i] > x:
			if arr[i] < c or c == -1:
				c = arr[i]
	return [f, c]


def getFloorAndCeil1(nums, n, x):
	nums.sort()
	floor = ceil = -1
	(left, right) = (0, n - 1)
	while left <= right:
		mid = (left + right) // 2
		val = nums[mid]
		if val == x:
			floor = ceil = val
			break
		elif val > x:
			ceil = val
			right = mid - 1
		else:
			floor = val
			left = mid + 1
	return [floor, ceil]

def getFloorAndCeil(nums, n, x):
	(floor, ceil) = (float('-inf'), float('inf'))
	for num in nums:
		if num <= x:
			floor = max(floor, num)
		if num >= x:
			ceil = min(ceil, num)
	if ceil == float('inf'):
		ceil = -1
	if floor == float('-inf'):
		floor = -1
	return [floor, ceil]


def getFloorAndCeil(nums, n, x):
	nums.sort()
	floor = ceil = -1
	(left, right) = (0, n - 1)
	while left <= right:
		mid = (left + right) // 2
		val = nums[mid]
		if val == x:
			floor = ceil = val
			break
		elif val > x:
			ceil = val
			right = mid - 1
		else:
			floor = val
			left = mid + 1
	return [floor, ceil]


def getFloorAndCeil(A, n, X):
	A.sort()
	low = 0
	high = n - 1
	floor = -1
	ceil = -1
	while low <= high:
		mid = low + (high - low) // 2
		if A[mid] == X:
			return (X, X)
		elif A[mid] > X:
			ceil = A[mid]
			high = mid - 1
		elif A[mid] < X:
			floor = A[mid]
			low = mid + 1
	return (floor, ceil)


import sys

def getFloorAndCeil(arr, n, x):
	floor = -1
	ceil = sys.maxsize
	for i in range(n):
		if arr[i] > floor and arr[i] <= x:
			floor = arr[i]
		if arr[i] >= x and arr[i] < ceil:
			ceil = arr[i]
	if ceil == sys.maxsize:
		return (floor, -1)
	return (floor, ceil)


def getFloorAndCeil(arr, n, x):
	floor = -1
	ceil = -1
	boo = True
	for el in arr:
		if el <= x and el > floor:
			floor = el
		if el >= x and boo:
			ceil = el
			boo = False
		if el >= x and el < ceil:
			ceil = el
	return [floor, ceil]


import sys

def getFloorAndCeil(arr, n, x):
	l = 0
	r = n - 1
	floor = -1
	ceil = sys.maxsize
	for i in range(n):
		if arr[i] <= x:
			floor = max(arr[i], floor)
		if arr[i] >= x:
			ceil = min(arr[i], ceil)
	if ceil == sys.maxsize:
		ceil = -1
	return (floor, ceil)


def getFloorAndCeil(arr, n, x):
	max_ele = max(arr)
	(floor, ceil) = (-1, max_ele)
	for (idx, num) in enumerate(arr):
		if num > floor and num <= x:
			floor = num
		if num < ceil and num >= x:
			ceil = num
	if x > max_ele:
		ceil = -1
	return (floor, ceil)


def lowerbound(arr, x):
	(low, high) = (0, len(arr))
	while low < high:
		mid = (low + high) // 2
		if arr[mid] < x:
			low = mid + 1
		else:
			high = mid
	if low < len(arr):
		if arr[low] == x:
			return x
		low = low - 1
		if low >= 0:
			return arr[low]
		else:
			return -1
	else:
		return arr[-1]

def higherbound(arr, x):
	(low, high) = (0, len(arr))
	while low < high:
		mid = (low + high) // 2
		if x < arr[mid]:
			high = mid
		else:
			low = mid + 1
	if low < len(arr):
		return arr[low]
	else:
		return arr[-1] if arr[-1] >= x else -1

def getFloorAndCeil(arr, n, x):
	arr.sort()
	low = lowerbound(arr, x)
	high = higherbound(arr, x)
	if low == x:
		return (low, low)
	else:
		return (low, high)


def getFloorAndCeil(arr, n, x):
	floor = -1
	ceil = 1000000
	flag = False
	for i in range(n):
		if arr[i] <= x and floor < arr[i]:
			floor = arr[i]
		if arr[i] >= x and ceil > arr[i]:
			flag = True
			ceil = arr[i]
	if flag == False:
		ceil = -1
	return (floor, ceil)


def getFloorAndCeil(arr, n, x):
	arr.sort()
	res = [-1, -1]
	(low, high) = (0, n - 1)
	while low <= high:
		mid = (low + high) // 2
		if arr[mid] == x:
			return [arr[mid], arr[mid]]
		if arr[mid] < x:
			res[0] = arr[mid]
			low = mid + 1
		else:
			high = mid - 1
	(low, high) = (0, n - 1)
	while low <= high:
		mid = (low + high) // 2
		if arr[mid] == x:
			return [arr[mid], arr[mid]]
		if arr[mid] < x:
			low = mid + 1
		else:
			res[1] = arr[mid]
			high = mid - 1
	return res


def getFloorAndCeil(arr, n, x):
	(floor, ceil) = (-1, float('inf'))
	for e in arr:
		if e == x:
			floor = ceil = x
		elif e > x:
			ceil = min(ceil, e)
		elif e < x:
			floor = max(floor, e)
	ceil = -1 if ceil == float('inf') else ceil
	return (floor, ceil)


def getFloorAndCeil(arr, n, x):
	if x in arr:
		return (x, x)
	if x not in arr:
		arr.append(x)
	arr.sort()
	i = arr.index(x)
	if i == n:
		return (arr[i - 1], -1)
	elif i == 0:
		return (-1, arr[i + 1])
	return (arr[i - 1], arr[i + 1])


def getFloorAndCeil(arr, n, x):
	floor = -1
	ceil = -1
	for i in range(n):
		if arr[i] == x:
			floor = arr[i]
			ceil = arr[i]
			break
		elif arr[i] < x and floor < arr[i]:
			floor = arr[i]
		elif arr[i] > x and (ceil > arr[i] or ceil == -1):
			ceil = arr[i]
	return [floor, ceil]


def getFloorAndCeil(arr, n, x):
	floor = -1
	ceil = -1
	for i in arr:
		if i < x:
			floor = max(floor, i)
		elif i == x:
			floor = i
			ceil = i
		elif ceil == -1:
			ceil = i
		else:
			ceil = min(i, ceil)
	return [floor, ceil]


def getFloorAndCeil(arr, n, x):
	floor = -1
	ceil = -1
	for i in arr:
		if i == x:
			ceil = floor = i
			break
		if i > x:
			if ceil == -1:
				ceil = i
			if ceil > i:
				ceil = i
		if i < x:
			if floor == -1:
				floor = i
			if floor < i:
				floor = i
	return [floor, ceil]


def getFloorAndCeil(arr, n, x):
	l = 0
	h = n - 1
	res = -1
	arr.sort()
	f = -1
	while l <= h:
		mid = (l + h) // 2
		if arr[mid] <= x:
			f = arr[mid]
			l = mid + 1
		else:
			res = arr[mid]
			h = mid - 1
	if f == x:
		return [f, f]
	return [f, res]


def getFloorAndCeil(arr, n, x):
	f = -1
	c = 10 ** 6
	for i in range(n):
		if arr[i] == x:
			f = x
			c = x
			return (f, c)
		elif arr[i] > x:
			c = min(c, arr[i])
		elif arr[i] < x:
			f = max(f, arr[i])
	if c == 10 ** 6:
		c = -1
	return (f, c)


def getFloorAndCeil(arr, n, x):
	arr.sort()
	l = 0
	h = n - 1
	res = -1
	while l <= h:
		m = (l + h) // 2
		if arr[m] == x:
			res = arr[m]
			break
		elif arr[m] < x:
			l = m + 1
		else:
			res = arr[m]
			h = m - 1
	l = 0
	h = n - 1
	res1 = -1
	while l <= h:
		m = (l + h) // 2
		if arr[m] == x:
			res1 = arr[m]
			break
		elif arr[m] < x:
			res1 = arr[m]
			l = m + 1
		else:
			h = m - 1
	return [res1, res]


def getFloorAndCeil(arr, n, X):
	arr.sort()

	def floor():
		if X < arr[0]:
			return -1
		low = 0
		high = len(arr) - 1
		while low <= high:
			mid = (low + high) // 2
			if arr[mid] == X:
				return mid
			if arr[mid] > X:
				high = mid - 1
			else:
				low = mid + 1
		return low - 1

	def ceil():
		if X > arr[-1]:
			return -1
		low = 0
		high = len(arr) - 1
		while low <= high:
			mid = (low + high) // 2
			if arr[mid] == X:
				return mid
			if arr[mid] > X:
				high = mid - 1
			else:
				low = mid + 1
		return low
	ans = []
	ans1 = floor()
	if ans1 == -1:
		ans.append(-1)
	else:
		ans.append(arr[ans1])
	ans2 = ceil()
	if ans2 == -1:
		ans.append(-1)
	else:
		ans.append(arr[ans2])
	return ans


def getFloorAndCeil(arr, n, x):
	arr.sort()
	(start, end) = (0, n - 1)
	while start <= end:
		mid = (start + end) // 2
		if arr[mid] == x:
			return (arr[mid], arr[mid])
		elif arr[mid] < x:
			start = mid + 1
		else:
			end = mid - 1
	if end < 0:
		return (-1, arr[start])
	elif start >= n:
		return (arr[end], -1)
	else:
		return (arr[end], arr[start])


import sys
INT_MAX = sys.maxsize

def getFloorAndCeil(arr, n, x):
	lb = -1
	ub = INT_MAX
	for i in arr:
		if i <= x:
			lb = max(lb, i)
		if i >= x:
			ub = min(ub, i)
	if ub == INT_MAX:
		ub = -1
	return (lb, ub)


def getFloorAndCeil(arr, n, x):
	(floor_value, ceil_value) = (-1, -1)
	(floor_diff, ceil_diff) = (float('inf'), float('inf'))
	for elem in arr:
		if elem == x:
			floor_value = elem
			ceil_value = elem
			break
		elif elem > x:
			if elem - x < ceil_diff:
				ceil_diff = elem - x
				ceil_value = elem
		elif x - elem < floor_diff:
			floor_diff = x - elem
			floor_value = elem
	return (floor_value, ceil_value)


def boundSearch(A, X, compare):
	N = len(A)
	(low, high) = (0, N - 1)
	while low < high:
		mid = (low + high) // 2
		if compare(X, A[mid]):
			high = mid
		else:
			low = mid + 1
	return low

def getFloorAndCeil(arr, n, x):
	arr.sort()
	lower = lambda k, ele: k <= ele
	ind = boundSearch(arr, x, lower)
	if arr[ind] == x:
		return [arr[ind], arr[ind]]
	else:
		if ind == 0:
			return [-1, arr[ind]]
		if ind == n - 1 and x > arr[ind]:
			return [arr[ind], -1]
		return [arr[ind - 1], arr[ind]]


def getFloorAndCeil(arr, n, x):
	floor = float('-inf')
	ciel = float('inf')
	for n in arr:
		if n <= x:
			floor = max(floor, n)
		if n >= x:
			ciel = min(ciel, n)
	res = [-1, -1]
	if floor != float('-inf'):
		res[0] = floor
	if ciel != float('inf'):
		res[1] = ciel
	return res


def getFloorAndCeil(arr, n, x):
	floor = -1
	ceil = 100000
	floor_exists = False
	ceil_exists = False
	for i in range(n):
		if arr[i] < x:
			floor = max(floor, arr[i])
			floor_exists = True
		elif arr[i] == x:
			return [x, x]
		else:
			ceil = min(ceil, arr[i])
			ceil_exists = True
	if ceil_exists:
		return [floor, ceil]
	else:
		return [floor, -1]


def getFloorAndCeil(arr, n, x):
	f = []
	g = []
	a = float('-inf')
	b = float('inf')
	for i in arr:
		if i <= x:
			f.append(i)
			a = max(a, i)
		if i >= x:
			g.append(i)
			b = min(b, i)
	if a == float('-inf'):
		return (-1, b)
	elif b == float('inf'):
		return (a, -1)
	else:
		return (a, b)


def getFloorAndCeil(arr, n, x):
	arr.sort()
	(floor, ceil) = (-1, 10000000000)
	for i in range(n):
		if arr[i] <= x:
			floor = max(floor, arr[i])
		if arr[i] >= x:
			ceil = min(ceil, arr[i])
	if ceil == 10000000000:
		ceil = -1
	return (floor, ceil)


import math

def getFloorAndCeil(arr, n, x):
	a = math.inf
	b = -1
	for i in range(n):
		if x <= arr[i] < a:
			a = arr[i]
		if b < arr[i] <= x:
			b = arr[i]
	return (b, a if a != math.inf else -1)


def getFloorAndCeil(A, N, X):
	A.sort()
	(l, r) = (0, N - 1)
	res = -1
	re = -1
	while l <= r:
		mid = (l + r) // 2
		if A[mid] <= X:
			res = mid
			l = mid + 1
		else:
			r = mid - 1
	(l, r) = (0, N - 1)
	while l <= r:
		mid = (l + r) // 2
		if A[mid] >= X:
			re = mid
			r = mid - 1
		else:
			l = mid + 1
	ans = [-1, -1]
	if res > -1:
		ans[0] = A[res]
	if re > -1:
		ans[1] = A[re]
	return ans


import sys

def findFloor(A, N, x):
	l = 0
	h = N - 1
	res = -1
	while l <= h:
		mid = (l + h) // 2
		if A[mid] > x:
			h = mid - 1
		elif A[mid] < x:
			l = mid + 1
			res = mid
		else:
			return mid
	return res

def findCeil(A, N, x):
	l = 0
	h = N - 1
	res = -1
	while l <= h:
		mid = (l + h) // 2
		if A[mid] > x:
			h = mid - 1
			res = mid
		elif A[mid] < x:
			l = mid + 1
		else:
			return mid
	return res

def getFloorAndCeil(arr, n, x):
	(maxi_floor, mini_ceil) = (-1, sys.maxsize)
	for i in range(n):
		if arr[i] > maxi_floor and arr[i] <= x:
			maxi_floor = arr[i]
		if arr[i] < mini_ceil and arr[i] >= x:
			mini_ceil = arr[i]
	if mini_ceil == sys.maxsize:
		return (maxi_floor, -1)
	else:
		return (maxi_floor, mini_ceil)


def getFloorAndCeil(A, N, X):
	c = 10000000
	f = -1
	for i in A:
		if i >= X and i <= c:
			c = i
		if i <= X and i >= f:
			f = i
	if c == 10000000:
		c = -1
	return (f, c)


def getFloorAndCeil(arr, n, x):
	arr.sort()
	l = [0] * 2
	for i in range(n - 1, -1, -1):
		if arr[i] <= x:
			l[0] = arr[i]
			break
	for i in range(n):
		if arr[i] >= x:
			l[1] = arr[i]
			break
	flor = l[0]
	ceil = l[1]
	if flor == 0 and ceil != 0:
		return (-1, ceil)
	elif flor == 0 and ceil == 0:
		return (-1, -1)
	if flor != 0 and ceil == 0:
		return (flor, -1)
	else:
		return (flor, ceil)


import math

def getFloorAndCeil(arr, n, x):
	floor = math.floor(x)
	ceil = math.ceil(x)
	arr.sort()
	nearest_floor = floor_helper(arr, 0, n - 1, floor, -1)
	nearest_ceil = ceil_helper(arr, 0, n - 1, ceil, -1)
	return (nearest_floor, nearest_ceil)

def floor_helper(arr, low, high, k, nearest_k):
	if low > high:
		return nearest_k
	mid = int((low + high) / 2)
	if arr[mid] == k:
		return k
	if arr[mid] < k:
		nearest_k = arr[mid]
		low = mid + 1
	else:
		high = mid - 1
	return floor_helper(arr, low, high, k, nearest_k)

def ceil_helper(arr, low, high, k, nearest_k):
	if low > high:
		return nearest_k
	mid = int((low + high) / 2)
	if arr[mid] == k:
		return k
	if arr[mid] < k:
		low = mid + 1
	else:
		nearest_k = arr[mid]
		high = mid - 1
	return ceil_helper(arr, low, high, k, nearest_k)


def getFloorAndCeil(arr, n, x):
	f = -1
	c = -1
	arr.sort()
	for i in arr:
		if i <= x:
			f = i
	for i in arr:
		if i >= x:
			c = i
			break
	return (f, c)


def getFloorAndCeil(arr, n, x):
	floor_arr = []
	ceil_arr = []
	for n in arr:
		if n > x:
			ceil_arr.append(n)
		elif n < x:
			floor_arr.append(n)
		else:
			return [n, n]
	if len(floor_arr) > 0 and len(ceil_arr) > 0:
		return [max(floor_arr), min(ceil_arr)]
	elif len(floor_arr) > 0:
		return [max(floor_arr), -1]
	elif len(ceil_arr) > 0:
		return [-1, min(ceil_arr)]
	else:
		return [-1, -1]


def getFloorAndCeil(arr, n, x):
	arr.sort()
	l1 = []
	for i in arr:
		if i <= x:
			l1.append(i)
	l2 = []
	for i in arr:
		if i >= x:
			l2.append(i)
	l = []
	if len(l1) == 0:
		l.append(-1)
	else:
		l.append(max(l1))
	if len(l2) == 0:
		l.append(-1)
	else:
		l.append(min(l2))
	return l


def getFloorAndCeil(arr, n, x):
	mini = 99999
	realmini = -1
	maxi = -1
	for i in range(n):
		if arr[i] > maxi and arr[i] <= x:
			maxi = arr[i]
		if arr[i] < mini and arr[i] >= x:
			mini = arr[i]
	if mini == 99999:
		mini = realmini
	return (maxi, mini)


def getFloorAndCeil(arr, n, x):
	arr.sort()
	floor = -1
	ceiling = -1
	for i in range(len(arr)):
		if arr[i] <= x:
			floor = arr[i]
		if arr[i] >= x:
			ceiling = arr[i]
			break
	return (floor, ceiling)


def getFloorAndCeil(arr, n, x):
	max_num = -1
	min_num = 100000001
	for i in range(n):
		if arr[i] <= x:
			max_num = max(max_num, arr[i])
		if arr[i] >= x:
			min_num = min(min_num, arr[i])
	if min_num == 100000001:
		min_num = -1
	return (max_num, min_num)


def getFloorAndCeil(arr, n, x):
	arr.sort()
	b = 0
	e = n - 1
	while b <= e and e < n:
		mid = (b + e) // 2
		if arr[mid] < x:
			b = mid + 1
		elif arr[mid] > x:
			e = mid - 1
		elif arr[mid] == x:
			b = mid
			e = mid
			break
	if b == n:
		return [arr[e], -1]
	if e == -1:
		return [-1, arr[b]]
	return [arr[e], arr[b]]


def getFloorAndCeil(arr, n, x):
	(ans1, ans2) = (-1, -1)
	for i in range(n):
		if arr[i] <= x and (ans1 == -1 or arr[i] > ans1):
			ans1 = arr[i]
		if arr[i] >= x and (ans2 == -1 or arr[i] < ans2):
			ans2 = arr[i]
	return [ans1, ans2]


def getFloorAndCeil(arr, n, x):
	mini = -1
	maxi = 10 ** 10
	for i in range(n):
		if arr[i] <= x:
			mini = max(arr[i], mini)
		if arr[i] >= x:
			maxi = min(arr[i], maxi)
	if maxi == 10 ** 10:
		maxi = -1
	return [mini, maxi]


def getFloorAndCeil(arr, n, x):
	arr.sort()
	floor = -1
	ceil = -1
	for i in range(len(arr)):
		if arr[i] == x:
			floor = arr[i]
			ceil = arr[i]
			break
		elif arr[i] < x:
			findex = i
			floor = arr[i]
		elif arr[i] > x:
			cindex = i
			ceil = arr[i]
			break
	return (floor, ceil)


def getFloorAndCeil(arr, n, x):
	if x in arr:
		return (x, x)
	floor = []
	ciel = []
	f1 = 0
	c1 = 0
	for i in arr:
		if i < x:
			floor.append(i)
			f1 = 1
		else:
			ciel.append(i)
			c1 = 1
	floor.sort()
	ciel.sort()
	if f1 == 0 and c1 == 0:
		return (-1, -1)
	if f1 == 0 and c1 != 0:
		return (-1, ciel[0])
	if c1 == 0 and f1 != 0:
		return (floor[n - 1], -1)
	if f1 != 0 and c1 != 0:
		return (floor[len(floor) - 1], ciel[0])


def getFloorAndCeil(arr, n, x):
	maxfl = -1
	maxcl = 999999
	for i in range(n):
		if arr[i] > maxfl and arr[i] <= x:
			maxfl = arr[i]
		if arr[i] < maxcl and arr[i] >= x:
			maxcl = arr[i]
	if maxcl == 999999:
		maxcl = -1
	return [maxfl, maxcl]


def getFloorAndCeil(arr, n, x):
	(floor, ceil) = (-1, float('inf'))
	for i in range(n):
		if arr[i] <= x:
			floor = max(floor, arr[i])
		if arr[i] >= x:
			ceil = min(ceil, arr[i])
	return (floor, -1 if ceil == float('inf') else ceil)


def getFloorAndCeil(arr, n, x):
	floor = min(arr) - 1
	ceil = max(arr) + 1
	for i in arr:
		if i >= floor and i <= x:
			floor = i
		if i <= ceil and i >= x:
			ceil = i
	if ceil == max(arr) + 1 and floor == min(arr) - 1:
		return (-1, -1)
	if ceil == max(arr) + 1:
		return (floor, -1)
	if floor == min(arr) - 1:
		return (-1, ceil)
	return (floor, ceil)


def getFloorAndCeil(arr, n, x):
	min_grt = float('inf')
	max_sm = float('-inf')
	for elem in arr:
		if elem >= x and elem <= min_grt:
			min_grt = elem
		if elem <= x and elem >= max_sm:
			max_sm = elem
	return [max_sm if max_sm != float('-inf') else -1, min_grt if min_grt != float('inf') else -1]


def getFloorAndCeil(arr, n, x):
	(cidx, fidx) = (0, 0)
	cdist = fdist = 99999999
	for i in range(n):
		if arr[i] >= x and arr[i] - x < cdist:
			cdist = arr[i] - x
			cidx = i
		if arr[i] <= x and x - arr[i] < fdist:
			fdist = x - arr[i]
			fidx = i
	ans = []
	if fdist == 99999999:
		ans.append(-1)
	else:
		ans.append(arr[fidx])
	if cdist == 99999999:
		ans.append(-1)
	else:
		ans.append(arr[cidx])
	return ans


def getFloorAndCeil(arr, n, x):
	arr.sort()
	floor = min(arr)
	ceil = max(arr)
	if x < floor:
		floor = -1
	if x > ceil:
		ceil = -1
	start = 0
	end = n - 1
	while start <= end:
		mid = (start + end) // 2
		if arr[mid] <= x:
			floor = max(floor, arr[mid])
		if arr[mid] >= x:
			ceil = min(ceil, arr[mid])
		if arr[mid] >= x:
			end = mid - 1
		elif arr[mid] <= x:
			start = mid + 1
	return (floor, ceil)


def getFloorAndCeil(nums, n, target):
	start = 0
	end = n - 1
	floor = -1
	ceil = -1
	nums.sort()
	while start <= end:
		mid = start + (end - start) // 2
		if nums[mid] == target:
			floor = nums[mid]
			break
		elif nums[mid] > target:
			end = mid - 1
		elif nums[mid] < target:
			floor = nums[mid]
			start = mid + 1
	start = 0
	end = n - 1
	while start <= end:
		mid = start + (end - start) // 2
		if nums[mid] == target:
			ceil = nums[mid]
			break
		elif nums[mid] > target:
			ceil = nums[mid]
			end = mid - 1
		elif nums[mid] < target:
			start = mid + 1
	return (floor, ceil)


def getFloorAndCeil(arr, n, x):
	high = float('inf')
	low = 0
	lc = 0
	hc = float('inf')
	for i in range(n):
		if arr[i] <= x:
			lc = arr[i]
		if arr[i] >= x:
			hc = arr[i]
		low = max(low, lc)
		high = min(high, hc)
	if low == 0:
		return (-1, high)
	elif high == float('inf'):
		return (low, -1)
	else:
		return (low, high)


def getFloorAndCeil(arr, n, x):
	l = [-1, -1]
	arr.sort()
	for i in range(n):
		if arr[i] <= x:
			l[0] = arr[i]
		if arr[i] >= x:
			l[1] = arr[i]
			break
	return l


def getFloorAndCeil(arr, n, x):
	arr.sort()
	(l, r) = (0, len(arr) - 1)
	ceil = 100000000000000000000
	floor = -1
	while l <= r:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return [arr[mid], arr[mid]]
		elif arr[mid] > x:
			if arr[mid] < ceil:
				ceil = arr[mid]
			r = mid - 1
		elif arr[mid] < x:
			if arr[mid] > floor:
				floor = arr[mid]
			l = mid + 1
	if ceil == 100000000000000000000:
		ceil = -1
	return [floor, ceil]


def getFloorAndCeil(arr, n, x):
	flor = -1
	cel = 99999999999
	for ele in arr:
		if ele < x:
			flor = max(flor, ele)
		elif ele > x:
			cel = min(cel, ele)
		if ele == x:
			flor = x
			cel = x
			break
	if flor == -1 and cel != 99999999999:
		return (-1, cel)
	if flor != -1 and cel == 99999999999:
		return (flor, -1)
	if flor == -1 and cel == 99999999999:
		return (-1, -1)
	return (flor, cel)


def getFloorAndCeil(arr, n, x):
	l = []
	m = []
	for i in range(len(arr)):
		if arr[i] <= x:
			l.append(arr[i])
		elif arr[i] > x:
			m.append(arr[i])
		else:
			pass
	if x in arr:
		m.append(x)
	l = set(l)
	l = list(l)
	m = set(m)
	m = list(m)
	if len(l) >= 1:
		fl = max(l)
	else:
		fl = -1
	if len(m) >= 1:
		ce = min(m)
	else:
		ce = -1
	return (fl, ce)


def getFloorAndCeil(a, n, x):
	a.sort()
	if x < a[0]:
		return [-1, a[0]]
	l = 0
	h = n - 1
	if x > a[-1]:
		return [a[n - 1], -1]
	while l <= h:
		m = l + h >> 1
		if a[m] == x:
			return [a[m], a[m]]
		elif a[m] > x:
			if m != 0 and a[m - 1] < x:
				return [a[m - 1], a[m]]
			else:
				h = m - 1
		elif m != len(a) - 1 and a[m + 1] > x:
			return [a[m], a[m + 1]]
		else:
			l = m + 1


def getFloorAndCeil(arr, n, x):
	ce = 9999999
	fl = -1
	for i in arr:
		if i <= x and i >= fl:
			fl = i
		if i >= x and i <= ce:
			ce = i
	if ce == 9999999:
		return (fl, -1)
	return (fl, ce)


def getFloorAndCeil(arr, n, x):
	arr.sort()
	if x > arr[-1]:
		return (arr[-1], -1)
	elif x < arr[0]:
		return (-1, arr[0])
	else:
		i = 0
		f = n
		while i < f:
			m = (i + f) // 2
			if arr[m] > x:
				f = m
			else:
				i = m + 1
		floor = arr[i - 1]
		i = 0
		f = n
		while i < f:
			m = (i + f) // 2
			if arr[m] >= x:
				f = m
			else:
				i = m + 1
		ceil = arr[i]
		return (floor, ceil)


def getFloorAndCeil(arr, n, x):
	floor = -1
	ceil = -1
	arr.sort()
	for i in range(n):
		if arr[i] >= x:
			floor = arr[i]
			break
	for i in range(n - 1, -1, -1):
		if arr[i] <= x:
			ceil = arr[i]
			break
		else:
			ceil = -1
	return (ceil, floor)


def getFloorAndCeil(arr, n, x):
	ceil = -1
	floor = -1
	arr.sort()
	above = [i for i in arr if i >= x]
	down = [i for i in arr if i <= x]
	if above:
		ceil = above[0]
	if down:
		floor = down[-1]
	return (floor, ceil)