Given a sorted array with possibly duplicate elements. The task is to find indexes of first and last occurrences of an element X in the given array.
Note: If the element is not present in the array return {-1,-1} as pair.
 
Example 1:
Input:
N = 9
v[] = {1, 3, 5, 5, 5, 5, 67, 123, 125}
X = 5
Output:
2 5
Explanation:
Index of first occurrence of 5 is 2
and index of last occurrence of 5 is 5.
Example 2:
Input:
N = 9
v[] = {1, 3, 5, 5, 5, 5, 7, 123, 125}
X = 7
Output:
6 6
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function indexes() which takes the array v[] and an integer X as inputs and returns  the first and last occurrence of the element X. If the element is not present in the array return {-1,-1} as pair.
Can you solve the problem in expected time complexity?
Expected Time Complexity: O(Log(N))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ v[i], X ≤ 10^{18}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Complete search

Starter code: #User function Template for python3

class Solution:
    def indexes(self, v, x):
        # Your code goes here
    

Solutions:
class Solution:

	def indexes(self, v, x):
		res = []
		for i in range(len(v)):
			if v[i] == x:
				res.append(i)
		if len(res) == 0:
			return [-1, -1]
		else:
			return (res[0], res[-1])


from bisect import bisect_right, bisect_left

class Solution:

	def indexes(self, v, x):
		(a, b) = (bisect_left(v, x), bisect_right(v, x) - 1)
		if a >= len(v) or v[a] != x:
			return [-1, -1]
		return [a, b]


class Solution:

	def indexes(self, v, x):
		s = 0
		e = len(v) - 1
		leftAns = -1
		while s <= e:
			mid = (s + e) // 2
			if v[mid] == x:
				leftAns = mid
				e = mid - 1
			elif v[mid] > x:
				e = mid - 1
			else:
				s = mid + 1
		s = 0
		e = len(v) - 1
		rightAns = -1
		while s <= e:
			mid = (s + e) // 2
			if v[mid] == x:
				rightAns = mid
				s = mid + 1
			elif v[mid] > x:
				e = mid - 1
			else:
				s = mid + 1
		return (leftAns, rightAns)


class Solution:

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

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

	def indexes(self, v, x):
		first = self.first_pos(v, x)
		last = self.find_last(v, x)
		return [first, last]


class Solution:

	def indexes(self, v, x):
		leftIndex = -1
		rightIndex = -1
		for i in range(len(v)):
			if v[i] == x:
				if leftIndex == -1:
					leftIndex = i
					rightIndex = i
				else:
					rightIndex = i
		return [leftIndex, rightIndex]


class Solution:

	def indexes(self, v, x):
		left = -1
		right = -1
		for i in range(len(v)):
			if v[i] == x and left == -1:
				left = i
			elif v[i] == x:
				right = i
		if right == -1:
			right = left
		return (left, right)


class Solution:

	def indexes(self, v, x):
		first = -1
		last = -1
		left = 0
		right = len(v) - 1
		while left <= right:
			mid = (left + right) // 2
			if v[mid] == x:
				first = mid
				right = mid - 1
			elif v[mid] < x:
				left = mid + 1
			else:
				right = mid - 1
		left = 0
		right = len(v) - 1
		while left <= right:
			mid = (left + right) // 2
			if v[mid] == x:
				last = mid
				left = mid + 1
			elif v[mid] < x:
				left = mid + 1
			else:
				right = mid - 1
		return [first, last]


class Solution:

	def indexes(self, v, x):
		count = 0
		first = -1
		second = -1
		for i in range(len(v)):
			if v[i] == x and count == 0:
				first = i
				count += 1
			if v[i] == x and count == 1:
				second = i
		if count == 0:
			return [-1, -1]
		if count == 1 and second == -1:
			return [first, first]
		return [first, second]


class Solution:

	def indexes(self, v, x):
		a = [-1, -1]
		n = len(v)
		for i in range(n):
			if v[i] == x:
				a[0] = i
				break
		for j in range(n - 1, -1, -1):
			if v[j] == x:
				a[1] = j
				break
		return (a[0], a[1])


class Solution:

	def indexes(self, v, x):
		res = []
		if x in v:
			res.append(v.index(x))
			a = v[::-1]
			ss = a.index(x)
			ii = len(v) - 1 - ss
			res.append(ii)
		else:
			return [-1, -1]
		return res


class Solution:

	def indexes(self, v, x):
		arr = [-1, -1]
		result = []
		count = 0
		z1 = -1
		z2 = -1
		if x not in v:
			return arr
		else:
			z1 = v.index(x)
			for i in range(len(v) - 1, -1, -1):
				if v[i] == x:
					z2 = i
					break
		result.append(z1)
		result.append(z2)
		return result


class Solution:

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

	def indexes(self, v, x):
		l = r = self.binarySearch(v, x)
		if l >= 0:
			while l - 1 >= 0 and v[l - 1] == x:
				l -= 1
			while r + 1 < len(v) and v[r + 1] == x:
				r += 1
		return [l, r]


class Solution:

	def indexes(self, arr, x):
		n = len(arr)
		(first, last) = (-1, -1)
		(l, r) = (0, n - 1)
		while l <= r:
			mid = (l + r) // 2
			if arr[mid] >= x:
				r = mid - 1
			else:
				l = mid + 1
			if arr[mid] == x:
				first = mid
		if first == -1:
			return [-1, -1]
		(l, r) = (first, n - 1)
		while l <= r:
			mid = (l + r) // 2
			if arr[mid] <= x:
				l = mid + 1
			else:
				r = mid - 1
			if arr[mid] == x:
				last = mid
		return [first, last]


class Solution:

	def indexes(self, arr, x):
		n = len(arr)
		ans = []
		for i in range(n):
			if arr[i] == x:
				ans.append(i)
		if len(ans) != 0:
			return [ans[0], ans[-1]]
		return [-1, -1]


class Solution:

	def indexes(self, v, x):
		l = 0
		h = len(v) - 1
		index = -1
		while l <= h:
			m = l + (h - l) // 2
			if v[m] == x:
				index = m
				break
			elif v[m] > x:
				h = m - 1
			else:
				l = m + 1
		if index == -1:
			return [-1, -1]
		(l, r) = (index, index)
		while l >= 0:
			if v[l] != x:
				break
			l = l - 1
		while r < len(v):
			if v[r] != x:
				break
			r = r + 1
		return [l + 1, r - 1]


class Solution:

	def indexes(self, v, x):
		fst = -1
		sec = -1
		for i in range(len(v)):
			if v[i] == x:
				if fst == -1:
					fst = i
					sec = i
				else:
					sec = i
		return (fst, sec)


class Solution:

	def indexes(self, arr, x):
		f = -1
		l = -1
		n = len(arr)
		s = 0
		e = n - 1
		while s <= e:
			mid = (s + e) // 2
			if arr[mid] == x:
				f = mid
				e = mid - 1
			elif arr[mid] > x:
				e = mid - 1
			else:
				s = mid + 1
		s = f if f != -1 else 0
		e = n - 1
		while s <= e:
			mid = (s + e) // 2
			if arr[mid] == x:
				l = mid
				s = mid + 1
			elif arr[mid] > x:
				e = mid - 1
			else:
				s = mid + 1
		return (f, l)


class Solution:

	def indexes(self, arr, X):
		n = len(arr)
		first = -1
		last = -1
		start = 0
		end = n - 1
		while start <= end:
			mid = (start + end) // 2
			if arr[mid] == X:
				first = mid
				end = mid - 1
			elif arr[mid] < X:
				start = mid + 1
			else:
				end = mid - 1
		start = first if first != -1 else 0
		end = n - 1
		while start <= end:
			mid = (start + end) // 2
			if arr[mid] == X:
				last = mid
				start = mid + 1
			elif arr[mid] < X:
				start = mid + 1
			else:
				end = mid - 1
		return (first, last)


class Solution:

	def indexes(self, v, x):
		(le, ri) = (-1, -1)
		(a, b) = (0, len(v) - 1)
		while a <= b:
			mid = (a + b) // 2
			if v[mid] == x:
				le = mid
				b = mid - 1
			elif v[mid] > x:
				b = mid - 1
			else:
				a = mid + 1
		(a, b) = (0, len(v) - 1)
		while a <= b:
			mid = (a + b) // 2
			if v[mid] == x:
				ri = mid
				a = mid + 1
			elif v[mid] > x:
				b = mid - 1
			else:
				a = mid + 1
		return (le, ri)


class Solution:

	def indexes(self, v, x):
		l = []
		k = [-1, -1]
		for i in range(len(v)):
			if v[i] == x:
				l.append(i)
				break
		for j in reversed(range(len(v))):
			if v[j] == x:
				l.append(j)
				break
		if len(l) > 0:
			return l
		else:
			return k


class Solution:

	def indexes(self, v, x):
		n = len(v)
		z = []
		if x not in v:
			return (-1, -1)
		for i in range(len(v) - 1):
			if v[i] == x:
				a = i
				z.append(a)
			if v[i] == x and v[i + 1] != x:
				b = i
				z.append(b)
		if x in v and v[n - 1] == x:
			b = n - 1
			z.append(b)
		return (min(z), b)


class Solution:

	def indexes(self, v, x):
		(low, high) = (0, len(v) - 1)
		(highest, lowest) = (-1, -1)
		while low <= high:
			mid = low + (high - low) // 2
			if v[mid] == x and (mid == len(v) - 1 or v[mid + 1] != x):
				highest = mid
				break
			elif v[mid] > x:
				high = mid - 1
			else:
				low = mid + 1
		(low, high) = (0, len(v) - 1)
		while low <= high:
			mid = low + (high - low) // 2
			if v[mid] == x and (mid == 0 or v[mid - 1] != x):
				lowest = mid
				break
			elif v[mid] < x:
				low = mid + 1
			else:
				high = mid - 1
		return [lowest, highest]


class Solution:

	def indexes(self, v, x):
		a = []
		l = len(v)
		for i in range(l):
			if v[i] == x:
				a.append(i)
				break
		for j in range(l - 1, -1, -1):
			if v[j] == x:
				a.append(j)
				break
		if len(a) >= 2:
			return a
		else:
			a.append(-1)
			a.append(-1)
			return a


import bisect

class Solution:

	def indexes(self, v, x):
		if x not in v:
			return (-1, -1)
		a = bisect.bisect_left(v, x)
		b = bisect.bisect_right(v, x)
		return (a, b - 1)


class Solution:

	def first(self, arr, k):
		s = 0
		e = len(arr) - 1
		mn = -1
		while s <= e:
			m = (s + e) // 2
			if k == arr[m]:
				mn = m
				e = m - 1
			if k < arr[m]:
				e = m - 1
			if k > arr[m]:
				s = m + 1
		return mn

	def last(self, arr, k):
		s = 0
		e = len(arr) - 1
		mn = -1
		while s <= e:
			m = (s + e) // 2
			if k == arr[m]:
				mn = m
				s = m + 1
			if k < arr[m]:
				e = m - 1
			if k > arr[m]:
				s = m + 1
		return mn

	def indexes(self, v, x):
		f = self.first(v, x)
		l = self.last(v, x)
		return [f, l]


class Solution:

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


class Solution:

	def firstoccurence(self, arr, x, n):
		ans = -1
		left = 0
		right = n - 1
		while left <= right:
			mid = (left + right) // 2
			if arr[mid] == x:
				ans = mid
				right = mid - 1
			elif arr[mid] > x:
				right = mid - 1
			else:
				left = mid + 1
		return ans

	def lastoccurence(self, arr, x, n):
		ans = -1
		left = 0
		right = n - 1
		while left <= right:
			mid = (left + right) // 2
			if arr[mid] == x:
				ans = mid
				left = mid + 1
			elif arr[mid] > x:
				right = mid - 1
			else:
				left = mid + 1
		return ans

	def indexes(self, v, x):
		n = len(v)
		fo = self.firstoccurence(v, x, n)
		lo = self.lastoccurence(v, x, n)
		if fo == -1 and lo == -1:
			return [-1, -1]
		return [fo, lo]


class Solution:

	def indexes(self, v, x):
		l = 0
		h = len(v) - 1
		ans = [-1, -1]
		while l <= h:
			mid = (l + h) // 2
			if v[mid] == x:
				ans[0] = mid
				ans[1] = mid
				h = mid - 1
			elif v[mid] > x:
				h = mid - 1
			elif v[mid] < x:
				l = mid + 1
		l = 0
		h = len(v) - 1
		while l <= h:
			mid = (l + h) // 2
			if v[mid] == x:
				if mid > ans[0]:
					ans[1] = mid
				l = mid + 1
			elif v[mid] > x:
				h = mid - 1
			elif v[mid] < x:
				l = mid + 1
		return ans


class Solution:

	def indexes(self, v, x):
		lst = []
		fin_list = []
		not_list = [-1, -1]
		pre = False
		for i in range(0, len(v)):
			if v[i] == x:
				lst.append(i)
				pre = True
		if pre == False:
			return not_list
		else:
			fin_list.append(lst[0])
			fin_list.append(lst[-1])
			return fin_list


class Solution:

	def indexes(self, v, x):
		l = 0
		h = len(v) - 1
		Lres = -1
		Rres = -1
		while l <= h:
			mid = (l + h) // 2
			if v[mid] > x:
				h = mid - 1
			elif v[mid] < x:
				l = mid + 1
			else:
				Lres = mid
				h = mid - 1
		l = 0
		h = len(v) - 1
		while l <= h:
			mid = (l + h) // 2
			if v[mid] > x:
				h = mid - 1
			elif v[mid] < x:
				l = mid + 1
			else:
				Rres = mid
				l = mid + 1
		return (Lres, Rres)


class Solution:

	def indexes(self, v, x):
		last = 0
		for i in range(len(v)):
			if v[i] == x:
				last = i
		if last == 0 and v[0] != x:
			return [-1, -1]
		return [v.index(x), last]


class Solution:

	def indexes(self, v, x):
		start = 0
		N = len(v)
		ans = -1
		end = N - 1
		l = []
		while start <= end:
			mid = int((start + end) / 2)
			if v[mid] == x:
				ans = mid
				end = mid - 1
			elif v[mid] < x:
				start = mid + 1
			else:
				end = mid - 1
		l.append(ans)
		start = 0
		end = N - 1
		while start <= end:
			mid = int((start + end) / 2)
			if v[mid] == x:
				ans = mid
				start = mid + 1
			elif v[mid] < x:
				start = mid + 1
			else:
				end = mid - 1
		l.append(ans)
		l.sort()
		if ans != -1:
			l.append(ans)
		return l


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

class Solution:

	def indexes(self, v, x):
		return bs(v, x)


class Solution:

	def indexes(self, v, x):
		l = []
		m = 0
		for i in range(len(v)):
			if v[i] == x:
				l.append(i)
				m = 1
				break
		for i in range(len(v) - 1, -1, -1):
			if v[i] == x:
				l.append(i)
				break
		if m == 0:
			l.append(-1)
			l.append(-1)
		return l


class Solution:

	def indexes(self, v, x):
		if x not in v:
			return (-1, -1)
		i = 0
		count = 0
		while i < len(v):
			while i < len(v) - 1 and v[i] == x and (v[i] == v[i + 1]):
				count += 1
				i += 1
			i += 1
		ind = v.index(x)
		return (ind, ind + count)


class Solution:

	def indexes(self, v, x):
		if x not in v:
			return [-1, -1]
		else:
			i1 = v.index(x)
			v = v[::-1]
			i2 = v.index(x)
			i2 = len(v) - 1 - i2
			return [i1, i2]


class Solution:

	def indexes(self, v, x):
		count = 0
		if x not in v:
			return (-1, -1)
		for i in range(len(v)):
			if v[i] == x:
				count += 1
				if count == 1:
					first_ind = i
				last_ind = i
		return (first_ind, last_ind)


class Solution:

	def indexes(self, v, x):

		def leftbsearch(v, x):
			low = 0
			high = len(v) - 1
			while low <= high:
				mid = (low + high) // 2
				if v[mid] > x:
					high = mid - 1
				elif v[mid] < x:
					low = mid + 1
				elif mid == 0 or v[mid] != v[mid - 1]:
					return mid
				else:
					high = mid - 1
			return -1

		def rightbsearch(v, x):
			low = 0
			high = len(v) - 1
			while low <= high:
				mid = (low + high) // 2
				if v[mid] > x:
					high = mid - 1
				elif v[mid] < x:
					low = mid + 1
				elif mid == len(v) - 1 or v[mid] != v[mid + 1]:
					return mid
				else:
					low = mid + 1
			return -1
		A = leftbsearch(v, x)
		if A == -1:
			return [-1, -1]
		else:
			return [leftbsearch(v, x), rightbsearch(v, x)]


class Solution:

	def indexes(self, v, x):

		def search(x):
			start = 0
			end = len(v)
			while start < end:
				mid = start + (end - start) // 2
				if v[mid] < x:
					start = mid + 1
				else:
					end = mid
			return start
		first = search(x)
		last = search(x + 1) - 1
		if first <= last:
			return (first, last)
		else:
			return (-1, -1)


class Solution:

	def indexes(self, v, x):

		def search(x):
			l = 0
			r = len(v)
			while l < r:
				mid = (l + r) // 2
				if v[mid] < x:
					l = mid + 1
				else:
					r = mid
			return l
		first = search(x)
		last = search(x + 1) - 1
		if first <= last:
			return (first, last)
		else:
			return (-1, -1)


class Solution:

	def indexes(self, v, x):
		if x not in v:
			return [-1, -1]
		list1 = []
		list1.append(v.index(x))
		for i in range(len(v) - 1, -1, -1):
			if v[i] == x:
				list1.append(i)
				return list1


class Solution:

	def indexes(self, v, x):
		lst = []
		if x not in v:
			return [-1, -1]
		for i in range(len(v)):
			if v[i] == x:
				lst.append(i)
				break
		for j in range(len(v) - 1, -1, -1):
			if v[j] == x:
				lst.append(j)
				break
		return lst


class Solution:

	def indexes(self, v, x):
		f = -1
		l = -1
		n = len(v)
		for i in range(n):
			if v[i] == x:
				if f == -1:
					f = i
					l = i
				else:
					l = i
		return [f, l]


def lower_bound(A, L, R, K):
	pos = R + 1
	while L <= R:
		M = (L + R) // 2
		if A[M] >= K:
			pos = M
			R = M - 1
		else:
			L = M + 1
	return pos


class Solution:

	def indexes(self, v, x):
		start = -1
		for i in range(len(v)):
			if v[i] == x:
				start = i
		end = -1
		for i in range(len(v) - 1, -1, -1):
			if v[i] == x:
				end = i
		return [end, start]


class Solution:

	def indexes(self, v, x):
		if x in v:
			res = [v.index(x)]
			v.reverse()
			res.append(len(v) - v.index(x) - 1)
			return res
		return [-1, -1]


class Solution:

	def indexes(self, v, x):
		ind = []
		for index in range(len(v)):
			if v[index] == x:
				ind.append(index)
		return [ind[0], ind[-1]] if ind else [-1, -1]


class Solution:

	def indexes(self, v, x):

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

		def check2(arr, x):
			low = 0
			high = len(arr) - 1
			while low <= high:
				mid = (low + high) // 2
				if arr[mid] > x:
					high = mid - 1
				elif arr[mid] <= x:
					low = mid + 1
			return low
		x1 = check(v, x)
		x2 = check2(v, x)
		if x2 - x1 == 0:
			return [-1, -1]
		else:
			return [x1, x2 - 1]


class Solution:

	def indexes(self, v, x):
		left = 0
		right = len(v) - 1
		while left <= right:
			mid = (left + right) // 2
			mid_n = v[mid]
			if x == mid_n:
				r = l = mid
				while r < len(v) - 1:
					if v[r + 1] == x:
						r += 1
					else:
						break
				while l > 0:
					if v[l - 1] == x:
						l -= 1
					else:
						break
				return [l, r]
			if x >= mid_n:
				left = mid + 1
			else:
				right = mid - 1
		return [-1, -1]


class Solution:

	def indexes(self, v, x):
		left_index = -1
		right_index = -1
		left = 0
		right = len(v) - 1

		def left_most_index(left, right, left_index):
			while left <= right:
				mid = (left + right) // 2
				if v[mid] == x:
					left_index = mid
					right = mid - 1
				elif v[mid] > x:
					right = mid - 1
				else:
					left = mid + 1
			return left_index

		def right_most_index(left, right, right_index):
			while left <= right:
				mid = (left + right) // 2
				if v[mid] == x:
					right_index = mid
					left = mid + 1
				elif v[mid] > x:
					right = mid - 1
					a = right
				else:
					left = mid + 1
					b = left
			return right_index
		a = left_most_index(left, right, left_index)
		b = right_most_index(left, right, right_index)
		c = [a, b]
		return c


class Solution:

	def indexes(self, v, x):
		n = len(v)
		s = 0
		e = n - 1
		m = (s + e) // 2
		l = -1
		r = -1
		t = 0
		while s <= e:
			if (m - 1 >= 0 and v[m] == v[m - 1]) == x or v[m] == x:
				l = m
				e = m - 1
				t = 1
			elif v[m] > x:
				e = m - 1
			elif v[m] < x:
				s = m + 1
			m = (s + e) // 2
		if t == 0:
			return [-1, -1]
		s = 0
		e = n - 1
		m = (s + e) // 2
		while s <= e:
			if m + 1 < n and v[m] == v[m + 1] == x or v[m] == x:
				r = m
				s = m + 1
			elif v[m] > x:
				e = m - 1
			elif v[m] < x:
				s = m + 1
			m = (s + e) // 2
		return [l, r]


class Solution:

	def indexes(self, v, x):
		i = 0
		n = len(v)
		arr = v
		(start, end) = (-1, -1)
		while i < n:
			if arr[i] == x:
				start = i
				end = i
				i += 1
				while i < n and arr[i] == x:
					end = i
					i += 1
			else:
				i += 1
		return (start, end)


class Solution:

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


class Solution:

	def indexes(self, v, x):
		to_return = []
		n = len(v)
		try:
			to_return.append(v.index(x))
		except:
			to_return.append(-1)
		try:
			to_return.append(n - v[::-1].index(x) - 1)
		except:
			to_return.append(-1)
		return to_return


class Solution:

	def UpgradedBinarySearch(self, v, x, first):
		l = 0
		h = len(v) - 1
		ans = -1
		while l <= h:
			mid = l + (h - l) // 2
			if v[mid] == x:
				ans = mid
				if first == True:
					h = mid - 1
				else:
					l = mid + 1
			elif x < v[mid]:
				h = mid - 1
			else:
				l = mid + 1
		return ans

	def indexes(self, v, x):
		first_occ = self.UpgradedBinarySearch(v, x, first=True)
		last_occ = self.UpgradedBinarySearch(v, x, first=False)
		return (first_occ, last_occ)


from typing import List

class Solution:

	def lbinsearch(self, nums: List[int], target: int) -> int:
		left = 0
		right = len(nums) - 1
		while left < right:
			m = (left + right) // 2
			if nums[m] >= target:
				right = m
			else:
				left = m + 1
		if nums[left] == target:
			return left
		return -1

	def rbinsearch(self, nums: List[int], target: int) -> int:
		left = 0
		right = len(nums) - 1
		while left < right:
			m = (left + right + 1) // 2
			if nums[m] <= target:
				left = m
			else:
				right = m - 1
		if nums[left] == target:
			return left
		return -1

	def indexes(self, v, x):
		if len(v) == 0:
			return [-1, -1]
		left = self.lbinsearch(v, x)
		right = self.rbinsearch(v, x)
		return [left, right]


class Solution:

	def indexes(self, v, x):
		app = []
		low = -1
		high = -1
		for i in range(len(v)):
			if v[i] == x:
				low = i
				break
		for i in range(len(v)):
			if v[i] == x:
				high = i
		app.append(low)
		app.append(high)
		return app


class Solution:

	def indexes(self, v, x):
		first_index = self.find_first_index(v, x, len(v))
		last_index = self.find_last_index(v, x, len(v))
		return [first_index, last_index]

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

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


class Solution:

	def indexes(self, v, x):

		def index_position(v, x, p):
			(low, high) = (0, len(v) - 1)
			while low <= high:
				mid = (low + high) // 2
				if p == 'first':
					result = search_first(v, x, mid)
				else:
					result = search_last(v, x, mid)
				if result == 'found':
					return mid
				elif result == 'left':
					high = mid - 1
				elif result == 'right':
					low = mid + 1
			return -1

		def search_first(v, x, mid):
			if v[mid] == x:
				if mid - 1 >= 0 and v[mid - 1] == x:
					return 'left'
				else:
					return 'found'
			elif v[mid] < x:
				return 'right'
			else:
				return 'left'

		def search_last(v, x, mid):
			if mid == len(v) - 1 and v[mid] == x:
				return 'found'
			if v[mid] == x:
				if mid + 1 >= 0 and v[mid + 1] == x:
					return 'right'
				else:
					return 'found'
			elif v[mid] < x:
				return 'right'
			else:
				return 'left'
		res = [index_position(v, x, 'first'), index_position(v, x, 'second')]
		return res


class Solution:

	def indexes(self, v, x):
		n = len(v)
		first = -1
		last = -1
		for i in range(0, n):
			if x != v[i]:
				continue
			if first == -1:
				first = i
			last = i
		return (first, last)


class Solution:

	def indexes(self, v, x):
		if x not in v:
			return [-1, -1]
		maxi = 0
		res = []
		res.append(v.index(x))
		for i in range(len(v)):
			if v[i] == x:
				maxi = max(maxi, i)
		res.append(maxi)
		return res


class Solution:

	def indexes(self, v, x):
		start = -1
		end = -1
		l = 0
		h = len(v) - 1
		while l <= h:
			mid = (l + h) // 2
			if v[mid] < x:
				l = mid + 1
			elif v[mid] == x:
				if start != -1:
					if mid < start:
						start = mid
				else:
					start = mid
				h = mid - 1
			else:
				h = mid - 1
		l = 0
		h = len(v) - 1
		while l <= h:
			mid = (l + h) // 2
			if v[mid] < x:
				l = mid + 1
			elif v[mid] == x:
				if end != -1:
					if mid > end:
						end = mid
				else:
					end = mid
				l = mid + 1
			else:
				h = mid - 1
		return (start, end)


class Solution:

	def indexes(self, v, x):
		lo = 0
		n = len(v)
		hi = n - 1
		while lo <= hi:
			mid = lo + (hi - lo) // 2
			if v[mid] == x:
				s = mid
				e = mid
				while e + 1 <= n - 1 and v[e + 1] == x:
					e += 1
				while s - 1 >= 0 and v[s - 1] == x:
					s -= 1
				return [s, e]
			if v[mid] > x:
				hi = mid - 1
			else:
				lo = mid + 1
		return [-1, -1]


class Solution:

	def indexes(self, a, x):
		n = len(a)

		def firstOccurance(a, x, n):
			ans = -1
			st = 0
			end = n - 1
			mid = st + (end - st) // 2
			while st <= end:
				if a[mid] == x:
					ans = mid
					end = mid - 1
				elif x < a[mid]:
					end = mid - 1
				elif x > a[mid]:
					st = mid + 1
				mid = st + (end - st) // 2
			return ans

		def lastOccurance(a, x, n):
			ans = -1
			st = 0
			end = n - 1
			mid = st + (end - st) // 2
			while st <= end:
				if a[mid] == x:
					ans = mid
					st = mid + 1
				elif x < a[mid]:
					end = mid - 1
				elif x > a[mid]:
					st = mid + 1
				mid = st + (end - st) // 2
			return ans
		fo = firstOccurance(a, x, n)
		lo = lastOccurance(a, x, n)
		return (fo, lo)


class Solution:

	def indexes(self, v, x):
		if x in v:
			m = v.index(x)
			v.reverse()
			n = v.index(x)
			return [m, len(v) - n - 1]
		else:
			return [-1, -1]


class Solution:

	def indexes(self, v, x):
		for i in range(len(v)):
			if v[i] == x:
				a = i
				break
		for i in range(len(v)):
			if v[i] == x:
				b = i
		if x in v:
			return (a, b)
		else:
			return (-1, -1)


class Solution:

	def indexes(self, arr, x):
		i = 0
		f = len(arr) - 1
		d = -1
		while i <= f:
			m = (i + f) // 2
			if arr[m] > x:
				f = m - 1
			elif arr[m] < x:
				i = m + 1
			else:
				d = m
				f = m - 1
		fir = d
		if fir == -1:
			return (-1, -1)
		i = 0
		f = len(arr) - 1
		d = -1
		while i <= f:
			m = (i + f) // 2
			if arr[m] > x:
				f = m - 1
			elif arr[m] < x:
				i = m + 1
			else:
				d = m
				i = m + 1
		las = d
		return (fir, las)