Binary search is a search algorithm usually used on a sorted sequence to quickly find an element with a given value. In this problem we will evaluate how binary search performs on data that isn't necessarily sorted. An element is said to be binary searchable if, regardless of how the pivot is chosen the algorithm returns true.
For example:
	[2, 1, 3, 4, 6, 5] and target = 5, we cannot find 5. Because when the pivot is 4, we get element 6, then right pointer will move left, so we'll lose the opportunity to find target 5.
	[2, 1, 3, 4, 5, 6] and target = 5, we can find 5. Because wherever we choose the pivots, we'll find target at last.
Given an unsorted array of n distinct integers, return the number of elements that are binary searchable.
 
Example 1:
Input:
N = 3
arr[] = {1, 3, 2}
Output: 1
Explanation: However we choose the 
pivots, we will always find the 
number 1 when looking for it. 
This does not hold for 3 and 2.
Example 2:
Input:
N = 6
arr[] = {2, 1, 3, 5, 4, 6}
Output: 2
Explanation: 3 and 6 are the numbers 
guaranteed to be found in the same way.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function binarySearchable() which takes an integer n and an array Arr of size n as input and return the number of elements that are binary searchable.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ arr[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Greedy algorithms

Starter code: #User function Template for python3

class Solution:
    def binarySearchable(self, Arr, n):
        # code here 

Solutions:
class Solution:

	def binarySearchable(self, Arr, n):
		left = [0] * n
		right = [100000] * n
		left[0] = Arr[0]
		for i in range(1, n):
			left[i] = max(left[i - 1], Arr[i])
		right[n - 1] = Arr[n - 1]
		for i in range(n - 2, -1, -1):
			right[i] = min(right[i + 1], Arr[i])
		ans = 0
		for i in range(n):
			if i == 0 and right[1] > Arr[i]:
				ans += 1
			elif i == n - 1 and left[n - 2] < Arr[n - 1]:
				ans += 1
			elif left[i - 1] < Arr[i] < right[i + 1]:
				ans += 1
		return ans


class Solution:

	def binarySearchable(self, Arr, n):
		lmax = []
		lmin = []
		mini = 10 ** 9
		maxi = -10 ** 9
		for i in Arr:
			maxi = max(maxi, i)
			lmax.append(maxi)
		for i in Arr[::-1]:
			mini = min(mini, i)
			lmin.append(mini)
		lmin = lmin[::-1]
		count = 0
		for i in range(n):
			if i == 0:
				if lmin[i + 1] > Arr[i]:
					count = count + 1
				continue
			if i == n - 1:
				if lmax[i - 1] < Arr[i]:
					count = count + 1
				continue
			if Arr[i] > lmax[i - 1] and Arr[i] < lmin[i + 1]:
				count = count + 1
		return count


class Solution:

	def binarySearchable(self, Arr, n):
		arr = Arr
		ans = 0
		for i in range(1, n - 1):
			if arr[i] > arr[i - 1] and arr[i] < arr[i + 1]:
				ans += 1
		if arr[0] < arr[1]:
			ans += 1
		if arr[n - 1] > arr[n - 2]:
			ans += 1
		return ans


class Solution:

	def binarySearchable(self, arr, n):
		maxi = [arr[0]]
		for item in arr[1:]:
			maxi.append(max(item, maxi[-1]))
		mini = [arr[-1]]
		for i in range(1, n):
			mini.append(min(arr[-i - 1], mini[-1]))
		mini.reverse()
		count = 0
		for i in range(n):
			if arr[i] == maxi[i] and arr[i] == mini[i]:
				count += 1
		return count


class Solution:

	def binarySearchable(self, Arr, n):
		left = [0] * n
		right = [0] * n
		left[0] = Arr[0]
		right[-1] = Arr[-1]
		for i in range(1, n):
			left[i] = max(Arr[i], left[i - 1])
		for i in range(n - 2, -1, -1):
			right[i] = min(Arr[i], right[i + 1])
		c = 0
		for i in range(n):
			if left[i] <= Arr[i] <= right[i]:
				c += 1
		return c


class Solution:

	def binarySearchable(self, Arr, n):
		left = [0] * n
		right = [0] * n
		mx = -float('inf')
		for i in range(n):
			left[i] = mx
			mx = max(mx, Arr[i])
		mn = float('inf')
		for i in range(n - 1, -1, -1):
			right[i] = mn
			mn = min(mn, Arr[i])
		cnt = 0
		for i in range(n):
			if Arr[i] > left[i] and Arr[i] < right[i]:
				cnt += 1
		return cnt


class Solution:

	def binarySearchable(self, Arr, n):
		max_till_now = -1
		stack = []
		for i in Arr:
			if i >= max_till_now:
				max_till_now = i
				stack.append(i)
			else:
				while len(stack) > 0 and stack[-1] > i:
					stack.pop(-1)
		return len(stack)


class Solution:

	def binarySearchable(self, Arr, n):
		c = 0
		if Arr[0] <= Arr[1]:
			c += 1
		for i in range(1, n):
			if i == n - 1 and Arr[i] >= Arr[i - 1]:
				c += 1
			elif Arr[i] >= Arr[i - 1] and Arr[i] <= Arr[i + 1]:
				c += 1
			else:
				pass
		return c


class Solution:

	def binarySearchable(self, Arr, n):
		(maxLeft, minRight) = ([0] * n, [0] * n)
		(maxLeft[0], minRight[-1]) = (Arr[0], Arr[-1])
		for i in range(1, n):
			maxLeft[i] = max(maxLeft[i - 1], Arr[i])
			minRight[n - i - 1] = min(minRight[n - i], Arr[n - i - 1])
		return sum((maxLeft[i] <= Arr[i] <= minRight[i] for i in range(n)))


import math

class Solution:

	def binarySearchable(self, arr, n):
		leftMax = [0] * n
		rightMin = [0] * n
		max_ = -1
		for i in range(n):
			leftMax[i] = max_
			max_ = max(max_, arr[i])
		min_ = math.inf
		for i in range(n - 1, -1, -1):
			rightMin[i] = min_
			min_ = min(min_, arr[i])
		count = 0
		for i in range(n):
			if arr[i] > leftMax[i] and arr[i] < rightMin[i]:
				count += 1
		return count


class Solution:

	def binarySearchable(self, Arr, n):
		c = 0
		if n == 1:
			return 1
		if Arr[0] < Arr[1]:
			c += 1
		for i in range(1, n - 1):
			if Arr[i] >= Arr[i - 1] and Arr[i] <= Arr[i + 1]:
				c += 1
		if Arr[n - 1] >= Arr[n - 2]:
			c += 1
		return c
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		Arr = list(map(int, input().split()))
		ob = Solution()
		print(ob.binarySearchable(Arr, n))


import itertools

class Solution:

	def binarySearchable(self, Arr, n):
		N = len(Arr)
		s = [1] * len(Arr)
		m = float('-inf')
		for i in range(N):
			m = max(m, Arr[i])
			s[i] &= Arr[i] == m
		m = float('inf')
		for i in reversed(range(N)):
			m = min(m, Arr[i])
			s[i] &= Arr[i] == m
		return sum(s)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		Arr = list(map(int, input().split()))
		ob = Solution()
		print(ob.binarySearchable(Arr, n))


import itertools

class Solution:

	def binarySearchable(self, Arr, n):
		t1 = list(itertools.accumulate(Arr, max))
		t2 = list(itertools.accumulate(Arr[::-1], min))[::-1]
		return sum((x == y for (x, y) in zip(t1, t2)))
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		Arr = list(map(int, input().split()))
		ob = Solution()
		print(ob.binarySearchable(Arr, n))


class Solution:

	def binarySearchable(self, Arr, n):
		if n <= 1:
			return n
		leftMax = [float('-inf')] * n
		rightMin = [float('inf')] * n
		minV = float('inf')
		maxV = float('-inf')
		for i in range(n):
			minV = min(minV, Arr[n - i - 1])
			rightMin[n - i - 1] = minV
			maxV = max(maxV, Arr[i])
			leftMax[i] = maxV
		count = 0
		for i in range(n):
			if Arr[i] == leftMax[i] and rightMin[i] == Arr[i]:
				count += 1
		return count


class Solution:

	def binarySearchable(self, Arr, n):
		max_ans = set()
		max_left = 0
		min_right = float('inf')
		for i in range(len(Arr)):
			max_left = max(max_left, Arr[i])
			if max_left == Arr[i]:
				max_ans.add(Arr[i])
		ans = 0
		for i in range(len(Arr) - 1, -1, -1):
			min_right = min(min_right, Arr[i])
			if min_right == Arr[i] and Arr[i] in max_ans:
				ans += 1
		return ans


class Solution:

	def binarySearchable(self, Arr, n):
		dp1 = [0] * n
		dp2 = [0] * n
		dp1[0] = Arr[0]
		dp2[n - 1] = Arr[n - 1]
		for i in range(1, n):
			dp1[i] = max(Arr[i], dp1[i - 1])
		for i in range(n - 2, -1, -1):
			dp2[i] = min(Arr[i], dp2[i + 1])
		cnts = 0
		for i in range(n):
			if i == 0 and dp2[i + 1] > Arr[i] or (i == n - 1 and dp1[i - 1] < Arr[i]) or (dp1[i - 1] < Arr[i] and dp2[i + 1] > Arr[i]):
				cnts += 1
		return cnts


class Solution:

	def binarySearchable(self, Arr, n):
		max_hashmap = {}
		max_till_now = Arr[0]
		min_till_now = Arr[n - 1]
		ans = 0
		for i in range(n):
			max_hashmap[i] = max_till_now
			max_till_now = max(max_till_now, Arr[i])
		for i in range(n - 1, -1, -1):
			if min_till_now >= Arr[i] and max_hashmap[i] <= Arr[i]:
				ans += 1
			max_till_now = max(max_till_now, Arr[i])
		return ans


class Solution:

	def binarySearchable(self, arr, n):
		c = 0
		i = 1
		while i < n:
			if arr[i] >= arr[i - 1]:
				i += 1
				c += 1
			else:
				i += 2
		if arr[n - 1] > arr[n - 2]:
			c += 1
		return c


class Solution:

	def binarySearchable(self, a, n):
		import sys
		max_left = [0] * n
		max_left[0] = -1
		max_so_far = a[0]
		for i in range(1, n):
			max_left[i] = max_so_far
			max_so_far = max(max_so_far, a[i])
		min_right = [0] * n
		min_so_far = a[-1]
		min_right[-1] = sys.maxsize
		for i in range(n - 2, -1, -1):
			min_right[i] = min_so_far
			min_so_far = min(a[i], min_so_far)
		ans = 0
		for i in range(n):
			if a[i] > max_left[i] and a[i] < min_right[i]:
				ans += 1
		return ans


class Solution:

	def binarySearchable(self, Arr, n):
		curr_min = Arr[n - 1]
		curr_max = Arr[0]
		count = 0
		curr_index = 0
		left = [0 for x in range(n)]
		right = [0 for x in range(n)]
		for i in range(n):
			if Arr[i] >= curr_max:
				curr_max = Arr[i]
				left[i] = 1
		for i in range(n - 1, -1, -1):
			if Arr[i] <= curr_min:
				curr_min = Arr[i]
				right[i] = 1
		for i in range(n):
			if left[i] == 1 and right[i] == 1:
				count += 1
		return count


class Solution:

	def binarySearchable(self, arr, n):
		minArr = [0] * len(arr)
		minArr[0] = arr[0]
		for i in range(1, len(arr)):
			minArr[i] = max(arr[i], minArr[i - 1])
		maxArr = [0] * len(arr)
		maxArr[-1] = arr[-1]
		for i in range(n - 2, -1, -1):
			maxArr[i] = min(arr[i], maxArr[i + 1])
		ans = 0
		for i in range(n):
			if maxArr[i] == minArr[i] == arr[i]:
				ans += 1
		return ans


class Solution:

	def binarySearchable(self, Arr, n):
		leftArr = [0 for _ in range(n)]
		rightArr = [0 for _ in range(n)]
		MAX = -10 ** 10
		MIN = 10 ** 10
		for i in range(n):
			leftArr[i] = MAX
			MAX = max(MAX, Arr[i])
		for i in range(n - 1, -1, -1):
			rightArr[i] = MIN
			MIN = min(MIN, Arr[i])
		cnt = 0
		for i in range(n):
			if leftArr[i] < Arr[i] and rightArr[i] > Arr[i]:
				cnt += 1
		return cnt


class Solution:

	def binarySearchable(self, Arr, n):
		min_arr = [-1] * n
		max_arr = [-1] * n
		max_ele = 0
		min_ele = 10 ** 10
		for i in range(n):
			max_ele = max(max_ele, Arr[i])
			min_ele = min(min_ele, Arr[n - 1 - i])
			max_arr[i] = max_ele
			min_arr[n - 1 - i] = min_ele
		count = 0
		for i in range(n):
			if i == 0:
				if min_arr[i] >= Arr[i]:
					count += 1
			elif i == n - 1:
				if max_arr[i] <= Arr[i]:
					count += 1
			elif min_arr[i] >= Arr[i] and max_arr[i] <= Arr[i]:
				count += 1
		return count


class Solution:

	def binarySearchable(self, Arr, n):
		minm = [Arr[0]]
		maxm = [0 for i in range(n)]
		maxm[n - 1] = Arr[-1]
		for i in range(1, n):
			if Arr[i] > minm[-1]:
				minm.append(Arr[i])
			else:
				minm.append(minm[-1])
		for i in range(n - 2, -1, -1):
			if Arr[i] < maxm[i + 1]:
				maxm[i] = Arr[i]
			else:
				maxm[i] = maxm[i + 1]
		ans = 0
		for i in range(n):
			if i == 0:
				if maxm[i + 1] > Arr[i]:
					ans += 1
			elif i == n - 1:
				if minm[i - 1] < Arr[i]:
					ans += 1
			elif minm[i - 1] < Arr[i] and maxm[i + 1] > Arr[i]:
				ans += 1
		return ans


class Solution:

	def binarySearchable(self, Arr, n):
		outn = 0
		for i in range(n):
			if i == 0:
				if Arr[i] < Arr[i + 1]:
					outn = outn + 1
			elif i == n - 1:
				if Arr[i] > Arr[i - 1]:
					outn = outn + 1
			elif Arr[i] > Arr[i - 1] and Arr[i] < Arr[i + 1]:
				outn = outn + 1
		return outn


class Solution:

	def binarySearchable(self, Arr, n):
		mini = float('inf')
		maxi = -float('inf')
		for i in range(n - 1, -1, -1):
			mini = min(Arr[i], mini)
			maxi = max(Arr[i], maxi)
		c = 1 if mini == Arr[0] else 0
		c += 1 if maxi == Arr[-1] else 0
		for i in range(1, n - 1):
			if Arr[i] > mini and Arr[i] < maxi:
				if Arr[i] > Arr[i - 1] and Arr[i] < Arr[i + 1]:
					c += 1
		return c


class Solution:

	def binarySearchable(self, Arr, n):
		b = sorted(Arr)
		c = 0
		for i in range(n):
			if Arr[i] == b[i]:
				c += 1
			else:
				break
		return c


import bisect

class Solution:

	def binarySearchable(self, arr, n):
		mini = float('inf')
		maxi = -float('inf')
		for i in range(n - 1, -1, -1):
			mini = min(arr[i], mini)
			maxi = max(arr[i], maxi)
		count = 1 if mini == arr[0] else 0
		count += 1 if maxi == arr[-1] else 0
		for i in range(1, n - 1):
			if arr[i] > mini and arr[i] < maxi:
				if arr[i] > arr[i - 1] and arr[i] < arr[i + 1]:
					count += 1
		return count


class Solution:

	def binarySearchable(self, Arr, n):
		c = 0
		for i in range(n):
			if Arr[i] >= Arr[max(0, i - 1)] and Arr[i] <= Arr[min(n - 1, i + 1)]:
				c += 1
		return c


class Solution:

	def binarySearchable(self, Arr, n):
		leftMax = [float('-inf')] * n
		rightMin = [float('inf')] * n
		for i in range(1, n):
			leftMax[i] = max(Arr[i - 1], leftMax[i - 1])
		for i in range(n - 2, -1, -1):
			rightMin[i] = min(Arr[i + 1], rightMin[i + 1])
		cnt = 0
		for i in range(n):
			if Arr[i] > leftMax[i] and Arr[i] < rightMin[i]:
				cnt += 1
		return cnt


INT_MIN = -pow(2, 32)
INT_MAX = -(-pow(2, 32) + 1)

class Solution:

	def binarySearchable(self, Arr, n):
		max_to_left = [INT_MIN] * n
		min_to_right = [INT_MAX] * n
		for i in range(1, n):
			max_to_left[i] = max(max_to_left[i - 1], Arr[i - 1])
		for i in range(n - 2, -1, -1):
			min_to_right[i] = min(min_to_right[i + 1], Arr[i + 1])
		res = 0
		for i in range(n):
			if max_to_left[i] < Arr[i] and min_to_right[i] > Arr[i]:
				res += 1
		return res


class Solution:

	def binarySearchable(self, Arr, n):
		if len(Arr) == 0:
			return 0
		b_search = 0
		max_arr = []
		curr_max = Arr[0]
		for i in range(0, n):
			curr_max = max(curr_max, Arr[i])
			max_arr.append(curr_max == Arr[i])
		curr_min = Arr[-1]
		for j in range(n - 1, -1, -1):
			if max_arr[j]:
				curr_min = min(Arr[j], curr_min)
				if curr_min == Arr[j]:
					b_search += 1
		return b_search


class Solution:

	def binarySearchable(self, Arr, n):
		rightMin = [1000000.0] * n
		leftMax = [-1] * n
		rightMin[n - 1] = Arr[n - 1]
		leftMax[0] = Arr[0]
		for i in range(1, n):
			leftMax[i] = max(leftMax[i - 1], Arr[i])
		for i in range(n - 2, -1, -1):
			rightMin[i] = min(rightMin[i + 1], Arr[i])
		listt = []
		for i in range(n):
			if Arr[i] == rightMin[i] and Arr[i] == leftMax[i]:
				listt.append(Arr[i])
		return len(listt)