As a programmer, it is very necessary to maintain balance in the life.
Here is task for you to maintain a balance. Your task is to find whether a given number x is balanced with respect to a given array a[ ] which is sorted in non-decreasing order.
Given a sorted array a[ ], the ceiling of x is the smallest element in the array greater than or equal to x, and the floor of x is the greatest element smaller than or equal to x. The number 'x' is said to be balanced if the absolute difference between floor of x and x is equal to the absolute difference between ceil of x and x i.e. if absolute(x - floor(x, a[])) = absolute(ceil(x, a[]) - x).
If one of floor or ceil does not exist assume 'x' to be balanced.
Example 1:
Input:
N = 7  
x = 5
a[] = {1, 2, 8, 10, 10, 12, 19} 
Output: 
Balanced
Explanation: Here 2 is the floor value and 
8 is the ceil value and (5 - 2) = (8 - 5).  
Example 2:
Input:
N = 8  
x = 9 
a[] = {1, 2, 5, 7, 8, 11, 12, 15} 
Output: 
Not Balanced
Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function FindElement() that takes array a[ ], its size N and integer x as input parameters and returns the string "Balanced" if the absolute difference between floor of x and x is equal to the absolute difference between ceil of x and x or else returns string "Not Balanced".
Expected Time Complexity: O(LogN)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: #User function Template for python3

class Solution:
    def isBalanced(self,a,n,x):


Solutions:
class Solution:

	def isBalanced(self, arr, n, x):
		s = 0
		e = n - 1
		while s <= e:
			mid = (s + e) // 2
			if arr[mid] - x == x - arr[mid - 1]:
				return 'Balanced'
			elif x >= arr[mid]:
				s = mid + 1
			elif x < arr[mid]:
				e = mid - 1
			if arr[0] > x or x in arr:
				return 'Balanced'
		return 'Not Balanced'


def flr(arr, x):
	(st, en) = (0, len(arr) - 1)
	ans = None
	while st <= en:
		mid = (st + en) // 2
		if arr[mid] > x:
			en = mid - 1
		elif arr[mid] <= x:
			ans = arr[mid]
			st = mid + 1
		else:
			print('Nothing')
	return ans

def cl(arr, x):
	(st, en) = (0, len(arr) - 1)
	ans = None
	while st <= en:
		mid = (st + en) // 2
		if arr[mid] < x:
			st = mid + 1
		else:
			ans = arr[mid]
			en = mid - 1
	return ans

class Solution:

	def isBalanced(self, a, n, x):
		floor = flr(a, x)
		ceil = cl(a, x)
		if floor and ceil:
			if abs(floor - x) == abs(ceil - x):
				return 'Balanced'
			return 'Not Balanced'
		return 'Balanced'


class Solution:

	def isBalanced(self, a, n, x):
		s = 0
		e = n - 1
		if n == 1:
			return 'Balanced'
		while e >= s:
			m = (s + e) // 2
			if a[m] == x:
				return 'Balanced'
			elif a[m] > x:
				e = m - 1
			else:
				s = m + 1
		if m == 0 and a[m] < x:
			if a[m + 1] > x and x - a[m] == a[m + 1] - x:
				return 'Balanced'
			else:
				return 'Not Balanced'
		if m == n - 1 and a[m] > x:
			if a[m - 1] < x and x - a[m - 1] == a[m] - x:
				return 'Balanced'
			else:
				return 'Not Balanced'
		if m == 0 or m == n - 1:
			return 'Balanced'
		if a[m] < x:
			if a[m + 1] > x and x - a[m] == a[m + 1] - x:
				return 'Balanced'
			else:
				return 'Not Balanced'
		elif a[m] > x:
			if a[m - 1] < x and x - a[m - 1] == a[m] - x:
				return 'Balanced'
			else:
				return 'Not Balanced'


def ceilno(a, n, x):
	start = 0
	end = n - 1
	res = 0
	while start <= end:
		if a[0] > x:
			return 0
		mid = start + (end - start) // 2
		if a[mid] == x:
			return mid
		elif a[mid] < x:
			start = mid + 1
		else:
			res = mid
			end = mid - 1
	return a[res]

def floorno(a, n, x):
	start = 0
	end = n - 1
	res = 0
	while start <= end:
		if a[0] > x:
			return 0
		mid = start + (end - start) // 2
		if a[mid] == x:
			return mid
		elif a[mid] < x:
			res = mid
			start = mid + 1
		else:
			end = mid - 1
	return a[res]

class Solution:

	def isBalanced(self, a, n, x):
		f = ceilno(a, n, x)
		g = floorno(a, n, x)
		h = x - g
		v = f - x
		if h == v:
			return 'Balanced'
		elif v + h == 0:
			return 'Balanced'
		else:
			return 'Not Balanced'


class Solution:

	def isBalanced(self, a, n, x):
		maxi = a[0]
		for i in a:
			if i <= x:
				maxi = max(i, maxi)
			else:
				break
		mini = 999999
		for i in range(n - 1, -1, -1):
			if a[i] >= x:
				mini = min(mini, a[i])
			else:
				break
		if abs(x - maxi) == abs(mini - x):
			return 'Balanced'
		else:
			return 'Not Balanced'


class Solution:

	def isBalanced(self, a, n, x):
		k = -99999
		j = 9999999
		for i in range(n):
			if x > a[i]:
				k = max(k, a[i])
			if x < a[i]:
				j = min(j, a[i])
		if x in a:
			return 'Balanced'
		if k == -99999 or j == 9999999:
			return 'Balanced'
		elif x - k == j - x:
			return 'Balanced'
		return 'Not Balanced'


class Solution:

	def isBalanced(self, a, n, x):
		lis = []
		gis = []
		for i in range(n):
			if x > a[i]:
				lis.append(a[i])
			if x < a[i]:
				gis.append(a[i])
		lis.sort()
		gis.sort()
		if x in a:
			return 'Balanced'
		if len(lis) == 0 or len(gis) == 0:
			return 'Balanced'
		elif x - lis[-1] == gis[0] - x:
			return 'Balanced'
		return 'Not Balanced'


def NextSmallElement(arr, x):
	l = 0
	h = len(arr) - 1
	index = 0
	while l <= h:
		mid = (l + h) // 2
		if a[mid] < x:
			l = mid + 1
			index = a[mid]
		elif a[mid] == x:
			return a[mid]
		else:
			h = mid - 1
	return index

def NextGreaterElement(arr, x):
	l = 0
	h = len(arr) - 1
	index = 0
	while l <= h:
		mid = (l + h) // 2
		if a[mid] > x:
			h = mid - 1
			index = a[mid]
		elif a[mid] == x:
			return a[mid]
		else:
			l = mid + 1
	return index

class Solution:

	def isBalanced(self, a, n, x):
		f1 = NextSmallElement(a, x)
		f2 = NextGreaterElement(a, x)
		if f1 == 0 or f2 == 0:
			return 'Balanced'
		if abs(f1 - x) == abs(f2 - x):
			return 'Balanced'
		return 'Not Balanced'


class Solution:

	def isBalanced(self, a, n, x):
		i = 0
		j = n - 1
		floor = -1
		ceil = -1
		while i <= j:
			mid = int((i + j) / 2)
			if a[mid] == x:
				floor = mid
				ceil = mid
				break
			elif a[mid] < x:
				floor = mid
				i = mid + 1
			else:
				j = mid - 1
				ceil = mid
		if floor == -1 or ceil == -1:
			return 'Balanced'
		if abs(x - a[floor]) == abs(a[ceil] - x):
			return 'Balanced'
		return 'Not Balanced'


class Solution:

	def isBalanced(self, a, n, x):
		left = 0
		right = n - 1
		while right >= left:
			mid = (left + right) // 2
			if x <= a[0] or x >= a[n - 1]:
				return 'Balanced'
			if x == a[mid]:
				return 'Balanced'
			elif x < a[mid + 1] and x > a[mid]:
				if abs(a[mid + 1] - x) == abs(x - a[mid]):
					return 'Balanced'
				else:
					return 'Not Balanced'
			elif x > a[mid]:
				left = mid + 1
			else:
				right = mid - 1
		return 'Not Balanced'


import bisect

class Solution:

	def isBalanced(self, a, n, x):
		i = bisect.bisect_left(a, x)
		if i == n or i == 0 or a[i] == x:
			return 'Balanced'
		return 'Balanced' if abs(a[i] - x) == abs(a[i - 1] - x) else 'Not Balanced'


class Solution:

	def binarysearch1(self, arr, l, r, k):
		if l <= r:
			mid = (l + r) // 2
			if arr[mid] >= k:
				return self.binarysearch1(arr, l, mid - 1, k)
			else:
				return self.binarysearch1(arr, mid + 1, r, k)
		return l

	def binarysearch2(self, arr, l, r, k):
		if l <= r:
			mid = (l + r) // 2
			if arr[mid] <= k:
				return self.binarysearch2(arr, mid + 1, r, k)
			else:
				return self.binarysearch2(arr, l, mid - 1, k)
		return r

	def isBalanced(self, a, n, x):
		l = self.binarysearch1(a, 0, n - 1, x)
		r = self.binarysearch2(a, 0, n - 1, x)
		if l >= n or r < 0:
			return 'Balanced'
		elif abs(a[l] - x) == abs(a[r] - x):
			return 'Balanced'
		return 'Not Balanced'


class Solution:

	def ceilSearch(self, arr, low, high, x):
		if x <= arr[low]:
			return low
		if x > arr[high]:
			return -1
		mid = (low + high) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] < x:
			if mid + 1 <= high and x <= arr[mid + 1]:
				return mid + 1
			else:
				return self.ceilSearch(arr, mid + 1, high, x)
		elif mid - 1 >= low and x > arr[mid - 1]:
			return mid
		else:
			return self.ceilSearch(arr, low, mid - 1, x)

	def isBalanced(self, a, n, x):
		c = self.ceilSearch(a, 0, n - 1, x)
		if a[c] == x or c == 0 or c == -1:
			return 'Balanced'
		if a[c] - x == x - a[c - 1]:
			return 'Balanced'
		else:
			return 'Not Balanced'


class Solution:

	def isBalanced(self, a, n, x):
		if x in a:
			return 'Balanced'
		if a[0] > x or a[-1] < x:
			return 'Balanced'
		floor = x
		ceil = x
		for i in a:
			if i < x:
				floor = i
			if i > x:
				ceil = i
				break
		if abs(x - floor) != abs(x - ceil):
			return 'Not Balanced'
		return 'Balanced'


class Solution:

	def isBalanced(self, a, n, x):
		s = self.floor(a, x)
		t = self.ceil(a, x)
		if s == -1 or t == -1:
			return 'Balanced'
		a1 = abs(s - x)
		a2 = abs(t - x)
		if a1 == a2:
			return 'Balanced'
		else:
			return 'Not Balanced'

	def floor(self, arr, x):
		start = 0
		end = len(arr) - 1
		res = -1
		while start <= end:
			mid = start + (end - start) // 2
			if arr[mid] == x:
				return arr[mid]
			elif arr[mid] < x:
				res = arr[mid]
				start = mid + 1
			else:
				end = mid - 1
		return res

	def ceil(self, arr, x):
		start = 0
		end = len(arr) - 1
		res = -1
		while start <= end:
			mid = start + (end - start) // 2
			if arr[mid] == x:
				return arr[mid]
			elif arr[mid] < x:
				start = mid + 1
			elif arr[mid] > x:
				res = arr[mid]
				end = mid - 1
		return res


class Solution:

	def isBalanced(self, a, n, x):
		if a[0] >= x or a[n - 1] == x:
			return 'Balanced'
		start = 0
		end = n - 1
		while start < end:
			mid = (start + end) // 2
			if a[mid] == x:
				return 'Balanced'
			elif a[mid] > x:
				end = mid - 1
			else:
				start = mid + 1
		if a[start] == x:
			return 'Balanced'
		elif a[start] > x:
			if x - a[start - 1] == a[start] - x:
				return 'Balanced'
		elif x - a[start] == a[start + 1] - x:
			return 'Balanced'
		return 'Not Balanced'


class Solution:

	def leftFloor(self, arr, n, x):
		start = 0
		end = n - 1
		res = -1
		while start <= end:
			mid = (start + end) // 2
			if arr[mid] >= x:
				res = arr[mid]
				end = mid - 1
			else:
				start = mid + 1
		return res

	def rightCeil(self, arr, n, x):
		start = 0
		end = n - 1
		res = -1
		while start <= end:
			mid = (start + end) // 2
			if arr[mid] <= x:
				res = arr[mid]
				start = mid + 1
			else:
				end = mid - 1
		return res

	def isBalanced(self, a, n, x):
		f = self.leftFloor(a, n, x)
		c = self.rightCeil(a, n, x)
		if f == -1 or c == -1:
			return 'Balanced'
		if abs(f - x) == abs(x - c):
			return 'Balanced'
		else:
			return 'Not Balanced'


class Solution:

	def isBalanced(self, arr, n, x):
		if arr[0] > x:
			return 'Balanced'
		floor = self.getFloor(arr, 0, n - 1, x)
		ceil = self.getCeil(arr, 0, n - 1, x)
		if abs(x - floor) == abs(ceil - x):
			return 'Balanced'
		else:
			return 'Not Balanced'

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

	def getFloor(self, arr, low, high, x):
		if low == high or (arr[0] <= x and arr[1] > x):
			return arr[0]
		while low <= high:
			mid = (low + high) // 2
			if arr[mid] <= x:
				if low == high:
					return arr[mid]
				elif arr[mid + 1] > x:
					return arr[mid]
				else:
					low = mid + 1
			else:
				high = mid - 1


class Solution:

	def isBalanced(self, a, n, x):
		(floor, ceil) = (a[0], a[0])
		flag1 = 0
		flag2 = 0
		for i in range(n):
			if a[i] < x:
				floor = a[i]
				flag1 = 1
			elif a[i] == x:
				return 'Balanced'
			else:
				ceil = a[i]
				flag2 = 1
				if abs(x - floor) == abs(x - ceil):
					return 'Balanced'
				break
		return 'Not Balanced'


class Solution:

	def getfloor(self, a, x):
		low = 0
		high = len(a) - 1
		ans = -1
		while low <= high:
			mid = (low + high) // 2
			if a[mid] > x:
				high = mid - 1
			elif a[mid] < x:
				ans = mid
				low = mid + 1
			else:
				return mid
		return ans

	def getceil(self, a, x):
		low = 0
		high = len(a) - 1
		ans = -1
		while low <= high:
			mid = (low + high) // 2
			if a[mid] > x:
				ans = mid
				high = mid - 1
			elif a[mid] < x:
				low = mid + 1
			else:
				return mid
		return ans

	def isBalanced(self, a, n, x):
		floor = self.getfloor(a, x)
		ceil = self.getceil(a, x)
		if floor == -1 or ceil == -1:
			return 'Balanced'
		if abs(x - a[floor]) == abs(x - a[ceil]):
			return 'Balanced'
		else:
			return 'Not Balanced'


class Solution:

	def isBalanced(self, a, n, x):
		low = 0
		high = n - 1
		while low <= high:
			mid = low + (high - low) // 2
			if a[mid] == x:
				return 'Balanced'
			elif a[mid] < x and a[mid + 1] > x:
				if abs(a[mid] - x) == abs(a[mid + 1] - x):
					return 'Balanced'
				else:
					return 'Not Balanced'
			elif a[mid] > x and a[mid - 1] < x:
				if abs(a[mid] - x) == abs(a[mid - 1] - x):
					return 'Balanced'
				else:
					return 'Not Balanced'
			elif mid == 0:
				if x <= a[mid] or x == a[mid + 1]:
					return 'Balanced'
				else:
					return 'Not Balanced'
			elif mid == n - 1:
				if x >= a[mid] or x == a[mid - 1]:
					return 'Balanced'
				else:
					return 'Not Balanced'
			elif a[mid] < x:
				low = mid + 1
			else:
				high = mid - 1
		return 'Not Balanced'
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	x = int(input())
	ob = Solution()
	print(ob.isBalanced(a, n, x))


class Solution:

	def isBalanced(self, a, n, x):
		if x < a[0] or x > a[-1]:
			return 'Balanced'
		import bisect
		low = bisect.bisect_left(a, x)
		high = bisect.bisect_right(a, x)
		if a[low] != x:
			low -= 1
		if a[high - 1] == x:
			high -= 1
		if abs(x - a[low]) == abs(x - a[high]):
			return 'Balanced'
		return 'Not Balanced'


class Solution:

	def Floor(self, arr, target):
		start = 0
		end = len(arr) - 1
		ans = -1
		while start <= end:
			mid = (start + end) // 2
			if arr[mid] < target:
				ans = mid
				start = mid + 1
			elif arr[mid] > target:
				end = mid - 1
			elif arr[mid] == target:
				return mid
		return ans

	def Ceiling(self, arr, target):
		start = 0
		end = len(arr) - 1
		ans = -1
		while start <= end:
			mid = (start + end) // 2
			if arr[mid] < target:
				start = mid + 1
			elif arr[mid] > target:
				ans = mid
				end = mid - 1
			elif arr[mid] == target:
				return mid
		return ans

	def isBalanced(self, arr, n, target):
		floor_index = self.Floor(arr, target)
		ceil_index = self.Ceiling(arr, target)
		if floor_index == -1 or ceil_index == -1:
			return 'Balanced'
		floor = arr[floor_index]
		ceiling = arr[ceil_index]
		if abs(target - floor) == abs(ceiling - target):
			return 'Balanced'
		else:
			return 'Not Balanced'


class Solution:

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

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

	def isBalanced(self, a, n, x):
		f = self.floor(a, x)
		c = self.ceil(a, x)
		if f == -1 or c == -1:
			return 'Balanced'
		if abs(f - x) == abs(c - x):
			return 'Balanced'
		else:
			return 'Not Balanced'


class Solution:

	def isBalanced(self, a, n, x):

		def check(isfloor):
			l = 0
			h = n - 1
			res = -1
			while l <= h:
				m = l + (h - l) // 2
				if a[m] == x:
					return a[m]
				elif isfloor:
					if a[m] > x:
						h = m - 1
					else:
						res = a[m]
						l = m + 1
				elif a[m] > x:
					res = a[m]
					h = m - 1
				else:
					l = m + 1
			return res
		p = check(True)
		q = check(False)
		if p != -1 and q != -1:
			if abs(p - x) == abs(q - x):
				return 'Balanced'
			else:
				return 'Not Balanced'
		return 'Balanced'


class Solution:

	def isBalanced(self, a, n, x):
		if x < a[0]:
			return 'Balanced'
		if x > a[n - 1]:
			return 'Balanced'
		s = 0
		e = n - 1
		res = 0
		while s <= e:
			m = (s + e) // 2
			if a[m] == x:
				return 'Balanced'
			elif a[m] > x:
				e = m - 1
			else:
				res = s
				s = m + 1
		return 'Balanced' if abs(a[s] - x) == abs(a[e] - x) else 'Not Balanced'


class Solution:

	def isBalanced(self, a, n, x):
		lw = self.getlowidx(a, x)
		hg = self.gethighidx(a, x)
		if lw == -1 or hg == n:
			return 'Balanced'
		else:
			if a[lw + 1] == x:
				return 'Balanced'
			if x - a[lw] == a[hg] - x:
				return 'Balanced'
			else:
				return 'Not Balanced'

	def getlowidx(self, a, x):
		l = 0
		h = len(a) - 1
		while l <= h:
			m = l + (h - l) // 2
			if a[m] >= x:
				h = m - 1
			else:
				l = m + 1
		return h

	def gethighidx(self, a, x):
		l = 0
		h = len(a) - 1
		while l <= h:
			m = l + (h - l) // 2
			if a[m] <= x:
				l = m + 1
			else:
				h = m - 1
		return l


class Solution:

	def isBalanced(self, a, n, x):
		if n == 1:
			return 'Balanced'

		def getfloorceil(x):
			low = 0
			high = n - 1
			while low <= high:
				mid = (low + high) // 2
				if a[mid] == x:
					return mid
				elif a[mid] > x:
					high = mid - 1
				else:
					low = mid + 1
			return high

		def getceil(x):
			low = 0
			high = n - 1
			while low <= high:
				mid = (low + high) // 2
				if a[mid] == x:
					return mid
				elif a[mid] > x:
					high = mid - 1
				else:
					low = mid + 1
			return low
		fl = getfloorceil(x)
		if fl < 0:
			return 'Balanced'
		cl = fl if a[fl] == x else fl + 1
		if cl >= n:
			return 'Balanced'
		return 'Balanced' if abs(a[fl] - x) == abs(a[cl] - x) else 'Not Balanced'


class Solution:

	def isBalanced(self, a, n, x):
		if x < a[0] or x > a[n - 1]:
			return 'Balanced'
		elif abs(x - self.floor(a, n, x)) == abs(x - self.ceil(a, n, x)):
			return 'Balanced'
		else:
			return 'Not Balanced'

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

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