Given an array where each element (arr[i]) represents the height of the tower. Find for each tower, the nearest possible tower that is shorter than it. You can look left or right on both sides.
Note : 
	
	If two smaller towers are at the same distance, pick the smallest tower.
	
	
	If two towers have the same height then we choose the one with a smaller index.
	
Example 1:
Input: 
arr[] = {1,3,2}
Output: 
{-1,0,0}
Explanation:
For 0th Index : no tower is smallest, so -1.
For 1st Index : For 3, here 1 & 2 both are 
small & at a same distance, so we will pick 1, 
beacuse it has smallest value, so 0(Index)
For 2nd Index : here 1 is smaller, so 0(Index)
So the final output will be which consistes 
Indexes are {-1,0,0}.
Example 2:
Input: 
arr[] = {4,8,3,5,3}
Output: 
{2,2,-1,2,-1}
Explanation: 
For 0th Index : here 3 is the smaller, so 2(Index) 
For 1st Index : For 8, here 4 & 3 both are
small & at a same distance, so we will pick 3, so 2(Index)
For 2nd Index : no tower is smallest, so -1.
For 3rd Index : For 5, here 3 & 3 both are
small & at a same distance, so we will pick 
3(2nd Index) because it smaller Index, so 2(Index)
For 4th Index : no tower is smallest, so -1.
So the final output will be which consistes
Indexes are {2,2,-1,2,-1}.
Your Task:
You don't need to read input or print anything. Your task is to complete the function nearestSmallerTower() which takes an array of heights of the towers as input parameter and returns an array of indexes of the nearest smaller tower. If there is no smaller tower on both sides then return -1 for that tower.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N) 
Constraints:
1 <= N <= 10^{5}
1 <= arr[i] <= 10^{5}

Difficulty: MEDIUM
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3



class Solution:

    def nearestSmallestTower(self,arr):

        #code here

Solutions:
class Solution:

	def nearestsmallRight(self, arr, n):
		st = [(arr[-1], n - 1)]
		ans = [(-1, i) for i in range(n)]
		ans[-1] = (-1, -1)
		for i in range(n - 2, -1, -1):
			if arr[i] <= st[-1][0]:
				while len(st) > 0 and arr[i] <= st[-1][0]:
					st.pop()
				if len(st) != 0:
					ans[i] = st[-1]
			else:
				ans[i] = st[-1]
			st.append((arr[i], i))
		return ans

	def nearestsmallLeft(self, arr, n):
		st = [(arr[0], 0)]
		ans = [(-1, i) for i in range(n)]
		ans[0] = (-1, -1)
		for i in range(1, n):
			if arr[i] <= st[-1][0]:
				while len(st) > 0 and arr[i] <= st[-1][0]:
					st.pop()
				if len(st) != 0:
					ans[i] = st[-1]
			else:
				ans[i] = st[-1]
			st.append((arr[i], i))
		return ans

	def nearestSmallestTower(self, arr):
		n = len(arr)
		ans = [-1 for i in range(n)]
		r = self.nearestsmallRight(arr, n)
		l = self.nearestsmallLeft(arr, n)
		for i in range(n):
			if r[i][0] == -1 and l[i][0] == -1:
				ans[i] = -1
			elif r[i][0] != -1 and l[i][0] != -1:
				if abs(i - r[i][1]) < abs(i - l[i][1]):
					ans[i] = r[i][1]
				elif abs(i - r[i][1]) > abs(i - l[i][1]):
					ans[i] = l[i][1]
				elif r[i][0] < l[i][0]:
					ans[i] = r[i][1]
				else:
					ans[i] = l[i][1]
			elif r[i][0] != -1:
				ans[i] = r[i][1]
			else:
				ans[i] = l[i][1]
		return ans


class Solution:

	def nr(self, a):
		s = []
		n = len(a)
		s.append(0)
		ns = [-1] * n
		for i in range(1, n):
			while s and a[s[-1]] > a[i]:
				ns[s[-1]] = i
				s.pop()
			s.append(i)
		return ns

	def nl(self, a):
		s = []
		n = len(a)
		s.append(n - 1)
		ns = [-1] * n
		for i in range(n - 2, -1, -1):
			while s and a[s[-1]] > a[i]:
				ns[s[-1]] = i
				s.pop()
			s.append(i)
		return ns

	def nearestSmallestTower(self, arr):
		a1 = self.nr(arr)
		a2 = self.nl(arr)
		n = len(arr)
		ans = [0] * n
		for i in range(n):
			if a1[i] != -1 and a2[i] != -1:
				if a1[i] - i < i - a2[i]:
					ans[i] = a1[i]
				elif a1[i] - i == i - a2[i]:
					if arr[a1[i]] < arr[a2[i]]:
						ans[i] = a1[i]
					else:
						ans[i] = a2[i]
				else:
					ans[i] = a2[i]
			else:
				ans[i] = max(a1[i], a2[i])
		return ans


class Solution:

	def nearestSmallestTower(self, arr):
		left_nearest_smaller = [-1] * len(arr)
		right_nearest_smaller = [-1] * len(arr)
		stack = [(-1, -1)]
		for i in range(len(arr)):
			while True:
				(j, h) = stack[-1]
				if h < arr[i]:
					break
				stack.pop()
			left_nearest_smaller[i] = j
			stack.append((i, arr[i]))
		stack = [(-1, -1)]
		for i in range(len(arr) - 1, -1, -1):
			while True:
				(j, h) = stack[-1]
				if h < arr[i]:
					break
				stack.pop()
			right_nearest_smaller[i] = j
			stack.append((i, arr[i]))
		for i in range(len(arr)):
			if left_nearest_smaller[i] == -1:
				left_nearest_smaller[i] = right_nearest_smaller[i]
				continue
			if right_nearest_smaller[i] == -1:
				right_nearest_smaller[i] = left_nearest_smaller[i]
				continue
			(j, k) = (left_nearest_smaller[i], right_nearest_smaller[i])
			if i - j > k - i:
				left_nearest_smaller[i] = k
			elif i - j < k - i:
				left_nearest_smaller[i] = j
			elif arr[k] < arr[j]:
				left_nearest_smaller[i] = k
			else:
				left_nearest_smaller[i] = j
		return left_nearest_smaller


class Solution:

	def nearestSmallestTower(self, arr):
		a = arr
		n = len(a)
		k = []
		t = min(a)
		for i in range(0, n):
			t1 = 0
			t2 = 0
			if a[i] == t:
				k.append(-1)
			else:
				if i + 1 < n:
					for r in range(i + 1, n):
						if a[r] < a[i]:
							t1 = 1
							break
				if i - 1 >= 0:
					for l in range(i - 1, -1, -1):
						if a[l] < a[i]:
							t2 = 1
							break
				if t1 == 0:
					k.append(l)
				elif t2 == 0:
					k.append(r)
				elif abs(i - r) > i - l:
					k.append(l)
				elif abs(i - r) < i - l:
					k.append(r)
				elif a[r] > a[l]:
					k.append(l)
				elif a[l] > a[r]:
					k.append(r)
				else:
					k.append(l)
		return k


class Solution:

	def nearestSmallestTower(self, arr):
		n = len(arr)
		stack = []
		left = [-1] * n
		right = [n] * n
		stack.append(0)
		for i in range(1, n):
			while len(stack) != 0 and arr[stack[-1]] >= arr[i]:
				stack.pop()
			if len(stack) != 0:
				left[i] = stack[-1]
			else:
				left[i] = -1
			stack.append(i)
		stack = []
		stack.append(n - 1)
		for i in range(n - 2, -1, -1):
			while len(stack) != 0 and arr[stack[-1]] >= arr[i]:
				stack.pop()
			if len(stack) != 0:
				right[i] = stack[-1]
			else:
				right[i] = n
			stack.append(i)
		ans = []
		for i in range(0, n):
			if left[i] == -1 and right[i] == n:
				ans.append(-1)
			elif left[i] == -1:
				ans.append(right[i])
			elif right[i] == n:
				ans.append(left[i])
			elif i - left[i] == right[i] - i:
				if arr[left[i]] < arr[right[i]]:
					ans.append(left[i])
				elif arr[left[i]] == arr[right[i]]:
					ans.append(min(left[i], right[i]))
				else:
					ans.append(right[i])
			elif i - left[i] < right[i] - i:
				ans.append(left[i])
			else:
				ans.append(right[i])
		return ans


class Solution:

	def calc(self, arr, n, a):
		i = 0
		s = [[i, arr[i]]]
		for i in range(1, n):
			k = len(s)
			(ind, val) = (s[k - 1][0], s[k - 1][1])
			if val > arr[i]:
				while s[len(s) - 1][1] > arr[i]:
					(ind, val) = s.pop(len(s) - 1)
					a[ind] = i
					if not len(s):
						break
			s.append([i, arr[i]])
		return a

	def nearestSmallestTower(self, arr):
		n = len(arr)
		a = [-1 for _ in range(len(arr))]
		rev_a = [-1 for _ in range(len(arr))]
		fin_a = [-1 for _ in range(len(arr))]
		a = self.calc(arr, n, a)
		rev_arr = arr[::-1]
		rev_a = self.calc(rev_arr, n, rev_a)
		rev_a = rev_a[::-1]
		for i in range(n):
			if rev_a[i] != -1:
				rev_a[i] = n - rev_a[i] - 1
		for i in range(n):
			if a[i] == -1 and rev_a[i] == -1:
				continue
			elif a[i] == -1:
				fin_a[i] = rev_a[i]
			elif rev_a[i] == -1:
				fin_a[i] = a[i]
			elif abs(i - a[i]) < abs(i - rev_a[i]):
				fin_a[i] = a[i]
			elif abs(i - a[i]) > abs(i - rev_a[i]):
				fin_a[i] = rev_a[i]
			elif arr[a[i]] < arr[rev_a[i]]:
				fin_a[i] = a[i]
			else:
				fin_a[i] = rev_a[i]
		return fin_a


class Solution:

	def nearestSmallestTower(self, arr):
		n = len(arr)
		st = []
		res = []
		prev = []
		next = []
		for i in range(n):
			while len(st) != 0 and arr[st[-1]] >= arr[i]:
				st.pop()
			if len(st) == 0:
				prev.append(-1)
				st.append(i)
			else:
				prev.append(st[-1])
				st.append(i)
		st = []
		for i in range(n - 1, -1, -1):
			while len(st) != 0 and arr[st[-1]] >= arr[i]:
				st.pop()
			if len(st) == 0:
				next.append(-1)
				st.append(i)
			else:
				next.append(st[-1])
				st.append(i)
		next = next[::-1]
		for i in range(n):
			if prev[i] == -1 and next[i] == -1:
				res.append(-1)
			elif prev[i] == -1:
				res.append(next[i])
			elif next[i] == -1:
				res.append(prev[i])
			elif i - prev[i] == next[i] - i:
				if arr[prev[i]] == arr[next[i]]:
					m = min(prev[i], next[i])
					res.append(m)
				elif arr[prev[i]] > arr[next[i]]:
					res.append(next[i])
				else:
					res.append(prev[i])
			elif i - prev[i] > next[i] - i:
				res.append(next[i])
			else:
				res.append(prev[i])
		return res


class Solution:

	def nearestSmallestTower(self, arr):
		left = [-1 for i in range(len(arr))]
		right = [-1 for i in range(len(arr))]
		res = [-1 for i in range(len(arr))]
		stack = []
		for i in range(len(arr)):
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			left[i] = stack[-1] if stack else -1
			stack.append(i)
		stack = []
		for i in range(len(arr) - 1, -1, -1):
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			right[i] = stack[-1] if stack else -1
			stack.append(i)
		for i in range(len(arr)):
			if left[i] == -1 and right[i] == -1:
				res[i] = -1
			elif left[i] == -1 and right[i] != -1:
				res[i] = right[i]
			elif left[i] != -1 and right[i] == -1:
				res[i] = left[i]
			else:
				dist1 = right[i] - i
				dist2 = i - left[i]
				if dist1 == dist2:
					res[i] = right[i] if arr[right[i]] < arr[left[i]] else left[i]
				else:
					res[i] = right[i] if dist1 < dist2 else left[i]
		return res


class Solution:

	def nearestSmallestTower(self, arr):
		smallest_height = min(arr)
		max_index = N - 1

		def check_both_sides(index):
			left_elem = 100000
			right_elem = 100000
			for i in range(1, len(arr)):
				if index - i >= 0:
					left_elem = arr[index - i]
				if index + i <= max_index:
					right_elem = arr[index + i]
				if left_elem < right_elem and left_elem < arr[index]:
					return index - i
				elif left_elem > right_elem and right_elem < arr[index]:
					return index + i
				elif left_elem == right_elem and left_elem < arr[index]:
					return index - i
		nearest_smallest_list = []
		for i in range(len(arr)):
			if arr[i] == smallest_height:
				nearest_smallest_list.append(-1)
			else:
				nearest_smallest_list.append(check_both_sides(i))
		return nearest_smallest_list


class Solution:

	def nearestSmallestTower(self, arr):
		n = len(arr)
		distLeft = [n + 1 for i in range(n)]
		distRight = [n + 1 for i in range(n)]
		stack = []
		for i in range(n):
			if not stack:
				distLeft[i] = -1
				stack.append([arr[i], i])
			else:
				while stack and stack[-1][0] >= arr[i]:
					stack.pop()
				if not stack:
					distLeft[i] = -1
				else:
					distLeft[i] = stack[-1][1]
				stack.append([arr[i], i])
		stack = []
		for i in range(n - 1, -1, -1):
			if not stack:
				distRight[i] = -1
				stack.append([arr[i], i])
			else:
				while stack and stack[-1][0] >= arr[i]:
					stack.pop()
				if not stack:
					distRight[i] = -1
				else:
					distRight[i] = stack[-1][1]
				stack.append([arr[i], i])
		res = [-1 for i in range(n)]
		for i in range(n):
			if distLeft[i] == -1:
				res[i] = distRight[i]
			elif distRight[i] == -1:
				res[i] = distLeft[i]
			else:
				(leftIndex, rightIndex) = (distLeft[i], distRight[i])
				(leftHeight, rightHeight) = (arr[leftIndex], arr[rightIndex])
				(distFromLeft, distFromRight) = (abs(i - leftIndex), abs(i - rightIndex))
				if distFromLeft == distFromRight:
					if rightHeight < leftHeight:
						res[i] = rightIndex
					else:
						res[i] = leftIndex
				elif distFromLeft < distFromRight:
					res[i] = leftIndex
				else:
					res[i] = rightIndex
		return res


from collections import deque

class Solution:

	def nearestSmallestTower(self, arr):
		res = []
		towers = deque()
		noTower = 9000000000.0
		for (index, tower) in enumerate(arr):
			if towers:
				while towers and arr[towers[-1]] >= tower:
					towers.pop()
				if towers:
					res.append(towers[-1])
				else:
					res.append(noTower)
			else:
				res.append(noTower)
			towers.append(index)
		towers = deque()
		for index in range(len(arr) - 1, -1, -1):
			tower = arr[index]
			if towers:
				while towers and arr[towers[-1]] >= tower:
					towers.pop()
				if towers:
					if res[index] == 9000000000.0:
						exsttwr = 9000000000.0
					else:
						exsttwr = arr[res[index]]
					currtwr = arr[towers[-1]]
					if min(currtwr, exsttwr) == 9000000000.0:
						res[index] = -1
					else:
						exstDist = abs(index - res[index])
						currDist = towers[-1] - index
						if exstDist == currDist:
							if currtwr < exsttwr:
								res[index] = towers[-1]
						elif currDist < exstDist:
							res[index] = towers[-1]
				elif res[index] == 9000000000.0:
					res[index] = -1
			elif res[index] == 9000000000.0:
				res[index] = -1
			towers.append(index)
		return res


class Solution:

	def nearestSmallestTower(self, arr):
		res = [float('inf') for i in range(len(arr))]
		forwardstack = []
		forwardstack.append(0)
		for i in range(1, len(arr)):
			while forwardstack and arr[forwardstack[-1]] >= arr[i]:
				forwardstack.pop()
			if forwardstack and arr[forwardstack[-1]] < arr[i]:
				res[i] = forwardstack[-1]
			forwardstack.append(i)
		backwardstack = [len(arr) - 1]
		for i in range(len(arr) - 2, -1, -1):
			while backwardstack and arr[backwardstack[-1]] >= arr[i]:
				backwardstack.pop()
			if backwardstack and arr[backwardstack[-1]] < arr[i]:
				if res[i] == float('inf'):
					res[i] = backwardstack[-1]
				else:
					if abs(backwardstack[-1] - i) < abs(res[i] - i):
						res[i] = backwardstack[-1]
					if abs(backwardstack[-1] - i) == abs(res[i] - i) and arr[backwardstack[-1]] < arr[res[i]]:
						res[i] = backwardstack[-1]
					if arr[backwardstack[-1]] == arr[res[i]] and backwardstack[-1] < res[i]:
						res[i] = backwardstack[-1]
			backwardstack.append(i)
		res = [i if i != float('inf') else -1 for i in res]
		return res


class Solution:

	def nearestSmallestTower(self, arr):
		n = len(arr)
		(small, greater) = ([-1 for i in range(n)], [-1 for i in range(n)])
		stack = []
		for i in range(n - 1, -1, -1):
			while stack and stack[-1][0] >= arr[i]:
				stack.pop()
			if stack:
				small[i] = stack[-1][-1]
			stack.append([arr[i], i])
		stack = []
		for i in range(n):
			while stack and stack[-1][0] >= arr[i]:
				stack.pop()
			if stack:
				greater[i] = stack[-1][-1]
			stack.append([arr[i], i])
		ans = [-1 for i in range(n)]
		for i in range(n):
			if small[i] == -1 and greater[i] == -1:
				continue
			if small[i] == -1:
				ans[i] = greater[i]
			elif greater[i] == -1:
				ans[i] = small[i]
			elif abs(small[i] - i) < abs(greater[i] - i):
				ans[i] = small[i]
			elif abs(greater[i] - i) < abs(small[i] - i):
				ans[i] = greater[i]
			elif arr[small[i]] < arr[greater[i]]:
				ans[i] = small[i]
			elif arr[greater[i]] < arr[small[i]]:
				ans[i] = greater[i]
			else:
				ans[i] = min(small[i], greater[i])
		return ans


class Solution:

	def nearestSmallestTower(self, arr):
		ans = []
		n = len(arr)
		stk = []
		right = [-1] * n
		for i in range(0, n):
			while len(stk) != 0 and arr[stk[-1]] > arr[i]:
				right[stk[-1]] = i
				stk.pop()
			stk.append(i)
		stk = []
		left = [-1] * n
		for i in range(n - 1, -1, -1):
			while len(stk) != 0 and arr[stk[-1]] > arr[i]:
				left[stk[-1]] = i
				stk.pop()
			stk.append(i)
		for i in range(n):
			if left[i] == -1 or right[i] == -1:
				ans.append(max(left[i], right[i]))
			elif abs(left[i] - i) == abs(right[i] - i) and arr[left[i]] == arr[right[i]]:
				ans.append(min(left[i], right[i]))
			elif abs(left[i] - i) == abs(right[i] - i):
				if arr[left[i]] < arr[right[i]]:
					ans.append(left[i])
				else:
					ans.append(right[i])
			elif abs(left[i] - i) > abs(right[i] - i):
				ans.append(right[i])
			else:
				ans.append(left[i])
		return ans


class Solution:

	def nearestSmallestTower(self, arr):
		suff = []
		n = len(arr)
		findsuff = [0] * n
		for i in range(n - 1, -1, -1):
			if len(suff) == 0:
				findsuff[i] = -1
				suff.append([arr[i], i])
			else:
				while suff:
					if suff[-1][0] < arr[i]:
						findsuff[i] = suff[-1][1]
						break
					suff.pop()
				if len(suff) == 0:
					findsuff[i] = -1
				suff.append([arr[i], i])
		pre = []
		findpre = [0] * n
		for i in range(n):
			if len(pre) == 0:
				findpre[i] = -1
				pre.append([arr[i], i])
			else:
				while pre:
					if pre[-1][0] < arr[i]:
						findpre[i] = pre[-1][1]
						break
					pre.pop()
				if len(pre) == 0:
					findpre[i] = -1
				pre.append([arr[i], i])
		new = [0] * n
		for i in range(n):
			if findsuff[i] == -1:
				new[i] = findpre[i]
				continue
			if findpre[i] == -1:
				new[i] = findsuff[i]
				continue
			if abs(findsuff[i] - i) == abs(findpre[i] - i):
				if arr[findsuff[i]] >= arr[findpre[i]]:
					new[i] = findpre[i]
				else:
					new[i] = findsuff[i]
			elif abs(findsuff[i] - i) > abs(findpre[i] - i):
				new[i] = findpre[i]
			else:
				new[i] = findsuff[i]
		return new


class Solution:

	def nearestSmallestTower(self, arr):
		n = len(arr)
		stackf = []
		stackfans = [None] * n
		stackb = []
		stackbans = [None] * n
		for i in range(n):
			if not stackf:
				stackfans[i] = -1
				stackf.append(i)
			elif arr[stackf[-1]] < arr[i]:
				stackfans[i] = stackf[-1]
				stackf.append(i)
			else:
				while stackf and arr[stackf[-1]] >= arr[i]:
					stackf.pop()
				if not stackf:
					stackfans[i] = -1
					stackf.append(i)
				else:
					stackfans[i] = stackf[-1]
					stackf.append(i)
			if not stackb:
				stackbans[n - i - 1] = -1
				stackb.append(n - i - 1)
			elif arr[stackb[-1]] < arr[n - i - 1]:
				stackbans[n - i - 1] = stackb[-1]
				stackb.append(n - i - 1)
			else:
				while stackb and arr[stackb[-1]] >= arr[n - i - 1]:
					stackb.pop()
				if not stackb:
					stackbans[n - i - 1] = -1
					stackb.append(n - i - 1)
				else:
					stackbans[n - i - 1] = stackb[-1]
					stackb.append(n - i - 1)
		for k in range(n):
			if stackfans[k] == -1 and stackbans[k] != -1:
				stackfans[k] = stackbans[k]
			elif stackfans[k] != -1 and stackbans[k] != -1 and (stackfans[k] != stackbans[k]):
				if abs(k - stackfans[k]) > abs(k - stackbans[k]):
					stackfans[k] = stackbans[k]
				elif abs(k - stackfans[k]) == abs(k - stackbans[k]):
					if arr[stackbans[k]] < arr[stackfans[k]]:
						stackfans[k] = stackbans[k]
		return stackfans


class Solution:

	def nearestSmallestTower(self, arr):
		leftSmallest = []
		rightSmallest = []
		stack = []
		for i in range(0, len(arr)):
			while len(stack) > 0:
				stackTopValue = stack[-1][0]
				stackTopPosition = stack[-1][1]
				if arr[i] > stackTopValue:
					leftSmallest.append([stackTopValue, stackTopPosition])
					break
				else:
					stack.pop()
			if len(stack) == 0:
				leftSmallest.append([-1, -1])
			stack.append([arr[i], i])
		stack = []
		for i in range(len(arr) - 1, -1, -1):
			while len(stack) > 0:
				stackTopValue = stack[-1][0]
				stackTopPosition = stack[-1][1]
				if arr[i] > stackTopValue:
					rightSmallest.append([stackTopValue, stackTopPosition])
					break
				else:
					stack.pop()
			if len(stack) == 0:
				rightSmallest.append([-1, -1])
			stack.append([arr[i], i])
		rightSmallest.reverse()
		finalAnswer = []
		for i in range(0, len(arr)):
			leftSmallestTowerValue = leftSmallest[i][0]
			leftSmallestTowerIndex = leftSmallest[i][1]
			rightSmallestTowerValue = rightSmallest[i][0]
			rightSmallestTowerIndex = rightSmallest[i][1]
			if leftSmallestTowerValue == -1:
				finalAnswer.append(rightSmallestTowerIndex)
			elif rightSmallestTowerValue == -1:
				finalAnswer.append(leftSmallestTowerIndex)
			else:
				distanceFromLeft = i - leftSmallestTowerIndex
				distanceFromRight = rightSmallestTowerIndex - i
				if distanceFromLeft < distanceFromRight:
					finalAnswer.append(leftSmallestTowerIndex)
				elif distanceFromLeft > distanceFromRight:
					finalAnswer.append(rightSmallestTowerIndex)
				elif leftSmallestTowerValue < rightSmallestTowerValue:
					finalAnswer.append(leftSmallestTowerIndex)
				elif leftSmallestTowerValue > rightSmallestTowerValue:
					finalAnswer.append(rightSmallestTowerIndex)
				else:
					finalAnswer.append(min(leftSmallestTowerIndex, rightSmallestTowerIndex))
		return finalAnswer


class Solution:

	def nearestSmallestTower(self, arr):
		SR = [[arr[0], 0]]
		D = {}
		R = [10 ** 10] * len(arr)
		for i in range(1, len(arr)):
			f = 0
			if len(SR) == 0:
				SR.append([arr[i], i])
			else:
				while SR[-1][0] > arr[i]:
					f = 1
					R[SR[-1][1]] = i
					SR.pop()
					if len(SR) == 0:
						break
				SR.append([arr[i], i])
		arrR = arr[::-1]
		SL = [[arrR[0], 0]]
		L = [10 ** 10] * len(arrR)
		for i in range(1, len(arrR)):
			f = 0
			if len(SL) == 0:
				SL.append([arrR[i], i])
			else:
				while SL[-1][0] > arrR[i]:
					f = 1
					L[SL[-1][1]] = len(arrR) - i - 1
					SL.pop()
					if len(SL) == 0:
						break
				SL.append([arrR[i], i])
		L.reverse()
		A = []
		for i in range(len(arr)):
			if L[i] == 10 ** 10 and R[i] == 10 ** 10:
				x = -1
			elif L[i] == 10 ** 10:
				x = R[i]
			elif R[i] == 10 ** 10:
				x = L[i]
			else:
				ld = i - L[i]
				rd = R[i] - i
				if ld == rd:
					if arr[L[i]] < arr[R[i]]:
						x = L[i]
					elif arr[L[i]] > arr[R[i]]:
						x = R[i]
					else:
						x = L[i]
				elif ld > rd:
					x = R[i]
				else:
					x = L[i]
			A.append(x)
		return A


class Solution:

	def nearestSmallestTower(self, arr):
		stack = [0]
		smallest_right = [-1] * len(arr)
		for j in range(1, len(arr)):
			if stack and arr[j] < arr[stack[-1]]:
				while stack and arr[j] < arr[stack[-1]]:
					k = stack.pop()
					smallest_right[k] = j
				stack.append(j)
			else:
				stack.append(j)
		stack = [len(arr) - 1]
		smallest_left = [-1] * len(arr)
		for j in range(len(arr) - 2, -1, -1):
			if stack and arr[j] < arr[stack[-1]]:
				while stack and arr[j] < arr[stack[-1]]:
					k = stack.pop()
					smallest_left[k] = j
				stack.append(j)
			else:
				stack.append(j)
		sol = [-1] * len(arr)
		for i in range(len(arr)):
			le = smallest_left[i]
			ri = smallest_right[i]
			if le != -1 and ri != -1:
				if abs(i - le) < abs(ri - i):
					sol[i] = le
				elif abs(i - le) > abs(ri - i):
					sol[i] = ri
				else:
					sol[i] = le if arr[le] <= arr[ri] else ri
			elif le == -1 and ri == -1:
				sol[i] = -1
			else:
				sol[i] = le + ri + 1
		return sol


class Solution:

	def nearestSmallestTower(self, arr):
		ans_arr = []
		arr1 = enumerate(arr)
		minimum = min(arr)
		for (inde, item) in enumerate(arr):
			if item == minimum:
				ans_arr.append(-1)
				continue
			if inde == 0:
				indd = inde
				for i in arr:
					if i < item:
						ans_arr.append(indd)
						break
					indd += 1
				continue
			if inde == len(arr) - 1:
				indd = inde
				for j in reversed(arr):
					if j < item:
						ans_arr.append(indd)
						break
					indd -= 1
				continue
			else:
				(k, l) = (inde - 1, inde + 1)
				while True:
					if arr[k] < item or arr[l] < item:
						if arr[k] == arr[l]:
							ans_arr.append(k)
							break
						elif arr[k] < arr[l]:
							ans_arr.append(k)
							break
						else:
							ans_arr.append(l)
							break
					if k > 0:
						k -= 1
					if l < len(arr) - 1:
						l += 1
				continue
		return ans_arr


class Solution:

	def nearestSmallestTower(self, arr):
		n = len(arr)
		ans1 = [-1 for _ in range(n)]
		ans2 = [-1 for _ in range(n)]
		ans = [-1 for _ in range(n)]
		st1 = [arr[0]]
		ps1 = [0]
		st2 = [arr[n - 1]]
		ps2 = [n - 1]
		for i in range(1, n):
			l = len(st1)
			while l > 0:
				if st1[-1] > arr[i]:
					st1.pop()
					temp = ps1.pop()
					ans1[temp] = i
					l = l - 1
				else:
					break
			st1.append(arr[i])
			ps1.append(i)
		for i in range(n - 2, -1, -1):
			l = len(st2)
			while l > 0:
				if st2[-1] > arr[i]:
					st2.pop()
					temp = ps2.pop()
					ans2[temp] = i
					l = l - 1
				else:
					break
			st2.append(arr[i])
			ps2.append(i)
		for i in range(n):
			if ans1[i] != -1 and ans2[i] != -1:
				t1 = ans1[i] - i
				t2 = i - ans2[i]
				if t1 == t2:
					t3 = arr[ans1[i]]
					t4 = arr[ans2[i]]
					if t3 < t4:
						ans[i] = ans1[i]
					else:
						ans[i] = ans2[i]
				elif t1 < t2:
					ans[i] = ans1[i]
				else:
					ans[i] = ans2[i]
			else:
				ans[i] = max(ans1[i], ans2[i])
		return ans


from collections import deque

class Solution:

	def nearestSmallestTower(self, arr):
		n = len(arr)
		stk = deque()
		rights = [-1] * n
		for i in range(n):
			while stk and stk[-1][0] > arr[i]:
				(cur, ind) = stk.pop()
				rights[ind] = i
			stk.append((arr[i], i))
		stk = deque()
		lefts = [-1] * n
		for i in range(n - 1, -1, -1):
			while stk and stk[-1][0] > arr[i]:
				(cur, ind) = stk.pop()
				lefts[ind] = i
			stk.append((arr[i], i))
		res = []
		for i in range(n):
			if lefts[i] == -1 and rights[i] == -1:
				res.append(-1)
			elif lefts[i] == -1 or rights[i] == -1:
				res.append(lefts[i] if lefts[i] != -1 else rights[i])
			elif i - lefts[i] == rights[i] - i:
				if arr[lefts[i]] == arr[rights[i]]:
					res.append(lefts[i])
				else:
					res.append(lefts[i] if arr[lefts[i]] < arr[rights[i]] else rights[i])
			else:
				res.append(lefts[i] if i - lefts[i] < rights[i] - i else rights[i])
		return res


class Solution:

	def nearestSmallestTower(self, arr):
		m = min(arr)
		ans = []
		for i in range(len(arr)):
			if m == arr[i]:
				ans.append(-1)
				continue
			f = 999999
			fv = 999999
			for j in reversed(range(0, i)):
				if arr[i] > arr[j]:
					f = j
					fv = arr[j]
					break
			e = 999999
			ev = 999999
			for j in range(i + 1, len(arr)):
				if arr[i] > arr[j]:
					e = j
					ev = arr[j]
					break
			if e == 999999:
				ans.append(f)
				continue
			if f == 999999:
				ans.append(e)
				continue
			if i - f == e - i:
				if fv < ev:
					ans.append(f)
				elif fv == ev:
					ans.append(f)
				else:
					ans.append(e)
			elif i - f > e - i:
				ans.append(e)
			elif i - f < e - i:
				ans.append(f)
		return ans


class Solution:

	def nearestSmallestTower(self, arr):
		INF = float('inf')
		n = len(arr)
		(left, right) = ([INF] * n, [INF] * n)
		stack = []
		for i in range(n):
			while stack and arr[stack[-1]] > arr[i]:
				idx = stack.pop()
				left[idx] = i
			stack.append(i)
		stack.clear()
		for i in range(n - 1, -1, -1):
			while stack and arr[stack[-1]] > arr[i]:
				idx = stack.pop()
				right[idx] = i
			stack.append(i)
		ans = []
		for i in range(n):
			if left[i] == INF and right[i] == INF:
				ans.append(-1)
			elif abs(left[i] - i) < abs(right[i] - i):
				ans.append(left[i])
			elif abs(left[i] - i) > abs(right[i] - i):
				ans.append(right[i])
			elif arr[left[i]] >= arr[right[i]]:
				ans.append(right[i])
			else:
				ans.append(left[i])
		return ans


class Solution:

	def nearestSmallestTower(self, arr):
		stack = []
		ans = []
		for i in range(len(arr)):
			while stack != [] and stack[-1][0] >= arr[i]:
				stack.pop()
			if stack == []:
				ans.append((99999, -1))
				stack.append((arr[i], i))
			else:
				ans.append(stack[-1])
				stack.append((arr[i], i))
		stack = []
		ans2 = []
		for i in range(len(arr) - 1, -1, -1):
			while stack != [] and stack[-1][0] >= arr[i]:
				stack.pop()
			if stack == []:
				ans2.append((99999, len(arr)))
				stack.append((arr[i], i))
			else:
				ans2.append(stack[-1])
				stack.append((arr[i], i))
		ans2 = ans2[::-1]
		res = []
		for i in range(len(arr)):
			if ans[i][0] == 99999 and ans2[i][0] == 99999:
				res.append(-1)
			elif ans[i][0] == 99999 and ans2[i][0] != 99999:
				res.append(ans2[i][1])
			elif ans2[i][0] == 99999 and ans[i][0] != 99999:
				res.append(ans[i][1])
			elif abs(i - ans[i][1]) == abs(i - ans2[i][1]):
				if ans[i][0] == ans2[i][0]:
					res.append(min(ans[i][1], ans2[i][1]))
				elif ans[i][0] < ans2[i][0]:
					res.append(ans[i][1])
				else:
					res.append(ans2[i][1])
			elif abs(i - ans[i][1]) > abs(i - ans2[i][1]):
				res.append(ans2[i][1])
			else:
				res.append(ans[i][1])
		return res


class Solution:

	def nearestSmallestTower(self, arr):
		n = len(arr)
		res = [-1] * n
		left = []
		right = []
		for i in range(n):
			while len(left) != 0 and arr[left[-1]] >= arr[i]:
				left.pop()
			if len(left) != 0:
				res[i] = left[-1]
			left.append(i)
		for i in range(n - 1, -1, -1):
			while len(right) != 0 and arr[right[-1]] >= arr[i]:
				right.pop()
			if len(right) != 0:
				if res[i] != -1:
					if abs(res[i] - i) == abs(right[-1] - i):
						if arr[res[i]] > arr[right[-1]]:
							res[i] = right[-1]
					elif abs(res[i] - i) > abs(right[-1] - i):
						res[i] = right[-1]
				else:
					res[i] = right[-1]
			right.append(i)
		return res


class Solution:

	def nearestSmallestTower(self, arr):
		s1 = []
		s2 = []
		z = [-1] * len(arr)
		for i in range(len(arr) - 1, -1, -1):
			while s1 and arr[s1[-1]] >= arr[i]:
				s1.pop()
			if s1:
				z[i] = s1[-1]
			else:
				z[i] = -1
			s1.append(i)
		for i in range(len(arr)):
			while s2 and arr[s2[-1]] >= arr[i]:
				s2.pop()
			if s2:
				if z[i] == -1:
					z[i] = s2[-1]
				else:
					index = s2[-1]
					if i - index < z[i] - i:
						z[i] = index
					elif i - index == z[i] - i:
						if arr[index] <= arr[z[i]]:
							z[i] = index
			s2.append(i)
		return z


class Solution:

	def nearestSmallestTower(self, arr):
		arrayLength = len(arr)
		prefix = [-1] * arrayLength
		suffix = [-1] * arrayLength
		stack = []
		for i in range(arrayLength):
			if len(stack) == 0:
				stack.append(i)
			else:
				while len(stack) != 0 and arr[i] < arr[stack[-1]]:
					prefix[stack[-1]] = i
					stack.pop()
				stack.append(i)
		stack = []
		for i in range(arrayLength - 1, -1, -1):
			if len(stack) == 0:
				stack.append(i)
			else:
				while len(stack) != 0 and arr[i] < arr[stack[-1]]:
					suffix[stack[-1]] = i
					stack.pop()
				stack.append(i)
		result = []
		for i in range(arrayLength):
			if prefix[i] == suffix[i] and suffix[i] == -1:
				result.append(-1)
			elif prefix[i] == -1:
				result.append(suffix[i])
			elif suffix[i] == -1:
				result.append(prefix[i])
			elif abs(i - prefix[i]) < abs(i - suffix[i]):
				result.append(prefix[i])
			elif abs(i - prefix[i]) > abs(i - suffix[i]):
				result.append(suffix[i])
			elif arr[suffix[i]] != arr[prefix[i]]:
				result.append(prefix[i] if arr[prefix[i]] < arr[suffix[i]] else suffix[i])
			else:
				result.append(prefix[i] if abs(i - prefix[i]) < abs(i - suffix[i]) else suffix[i])
		return result


class Solution:

	def nearestSmallestTower(self, arr):
		n = len(arr)
		left = [-1] * n
		right = [-1] * n
		st = []
		for i in range(n):
			while st and arr[st[-1]] >= arr[i]:
				st.pop()
			if st:
				left[i] = st[-1]
			st.append(i)
		st = []
		for i in range(n - 1, -1, -1):
			while st and arr[st[-1]] >= arr[i]:
				st.pop()
			if st:
				right[i] = st[-1]
			st.append(i)
		result = [0] * n
		for i in range(n):
			leftDist = i - left[i] if left[i] != -1 else float('inf')
			rightDist = right[i] - i if right[i] != -1 else float('inf')
			if leftDist < rightDist or (leftDist == rightDist and left[i] != -1 and (arr[left[i]] <= arr[right[i]])):
				result[i] = left[i]
			elif leftDist > rightDist or (leftDist == rightDist and right[i] != -1 and (arr[right[i]] < arr[left[i]])):
				result[i] = right[i]
			else:
				result[i] = -1
		return result


class Solution:

	def nearestSmallestTower(self, arr):
		res1 = []
		res2 = []
		s1 = []
		s2 = []
		z = [0] * len(arr)
		for i in range(len(arr) - 1, -1, -1):
			while s1 and arr[s1[-1]] >= arr[i]:
				s1.pop()
			if s1:
				z[i] = -1
			else:
				z[i] = s1[-1]
			s1.append(i)
		for i in range(len(arr)):
			while s2 and arr[s2[-1]] >= arr[i]:
				s2.pop()
			if s2:
				if z[i] == -1:
					z[i] = s2[-1]
				else:
					index = s2[-1]
					if i - index < z[i] - i:
						z[i] = index
					elif i - index == z[i] - i:
						if a[index] < a[z[i]]:
							z[i] = index
			s2.append(i)
		return z

class Solution:

	def nearestSmallestTower(self, a):
		n = len(a)
		st = []
		ans = [-1] * n
		for i in range(n - 1, -1, -1):
			while len(st) and a[st[-1]] >= a[i]:
				st.pop()
			if len(st):
				ans[i] = st[-1]
			else:
				ans[i] = -1
			st.append(i)
		while len(st):
			st.pop()
		for i in range(n):
			while len(st) and a[st[-1]] >= a[i]:
				st.pop()
			if len(st):
				if ans[i] == -1:
					ans[i] = st[-1]
				else:
					index = st[-1]
					if i - index < ans[i] - i:
						ans[i] = index
					elif i - index == ans[i] - i:
						if a[index] <= a[ans[i]]:
							ans[i] = index
			st.append(i)
		return ans


class Solution:

	def nearestSmallestTower(self, arr):
		res = []
		size = len(arr)
		sm = min(arr)
		for i in range(size):
			if arr[i] == sm:
				res.append(-1)
			else:
				j = 1
				p = -1
				q = -1
				while 1:
					if i - j >= 0 and arr[i - j] < arr[i]:
						p = i - j
					if i + j < size and arr[i + j] < arr[i]:
						q = i + j
					if p >= 0 and q >= 0:
						if arr[p] <= arr[q]:
							res.append(p)
						else:
							res.append(q)
						break
					elif p >= 0:
						res.append(p)
						break
					elif q >= 0:
						res.append(q)
						break
					else:
						j += 1
		return res


class Solution:

	def nearestSmallestTower(self, A):

		def _pre(r, out):
			stk = [(A[r.start], r.start)]
			for i in r[1:]:
				v = A[i]
				while stk and stk[-1][0] >= v:
					stk.pop()
				out[i] = INV if not stk else stk[-1][1]
				stk.append((v, i))
		(N, INV) = (len(A), 10 ** 9)
		(LL, LR) = ([INV] * N, [INV] * N)
		ans = [-1] * N
		_pre(range(N), LL)
		_pre(range(N - 1, -1, -1), LR)
		for i in range(N):
			if LL[i] == LR[i] == INV:
				continue
			(Ldif, Rdif) = (abs(i - LL[i]), abs(LR[i] - i))
			if Ldif < Rdif:
				ans[i] = LL[i]
			elif Ldif > Rdif:
				ans[i] = LR[i]
			elif A[LL[i]] <= A[LR[i]]:
				ans[i] = LL[i]
			else:
				ans[i] = LR[i]
		return ans


from collections import deque

class Solution:

	def nearestSmallestTower(self, arr):
		n = len(arr)
		(left, right) = (deque(), deque())
		ans = [-1] * n
		for i in range(n):
			while left and arr[left[-1]] >= arr[i]:
				left.pop()
			if left:
				ans[i] = left[-1]
			left.append(i)
		for i in range(n - 1, -1, -1):
			while right and arr[right[-1]] >= arr[i]:
				right.pop()
			if right:
				if ans[i] != -1:
					if abs(ans[i] - i) == abs(right[-1] - i):
						if arr[ans[i]] > arr[right[-1]]:
							ans[i] = right[-1]
					elif abs(ans[i] - i) > abs(right[-1] - i):
						ans[i] = right[-1]
				else:
					ans[i] = right[-1]
			right.append(i)
		return ans


class Solution:

	def nearestSmallestTower(self, arr):
		n = len(arr)
		ans = [-1] * n
		s1 = []
		for i in range(n):
			while s1 and arr[s1[-1]] >= arr[i]:
				s1.pop()
			if s1:
				ans[i] = s1[-1]
			s1.append(i)
		s1.clear()
		for i in range(n - 1, -1, -1):
			while s1 and arr[s1[-1]] >= arr[i]:
				s1.pop()
			if s1:
				if ans[i] == -1:
					ans[i] = s1[-1]
				elif i - ans[i] > s1[-1] - i:
					ans[i] = s1[-1]
				elif i - ans[i] == s1[-1] - i:
					if arr[ans[i]] > arr[s1[-1]]:
						ans[i] = s1[-1]
			s1.append(i)
		return ans


class Solution:

	def nearestSmallestTower(self, arr):
		n = len(arr)
		(pre, suf) = ([], [])
		res = [-1] * n
		for i in range(n):
			while pre and arr[pre[-1]] >= arr[i]:
				pre.pop()
			if pre:
				res[i] = pre[-1]
			pre.append(i)
		for i in range(n - 1, -1, -1):
			while suf and arr[suf[-1]] >= arr[i]:
				suf.pop()
			if suf:
				if res[i] != -1:
					if abs(res[i] - i) == abs(suf[-1] - i):
						if arr[res[i]] > arr[suf[-1]]:
							res[i] = suf[-1]
					elif abs(res[i] - i) > abs(suf[-1] - i):
						res[i] = suf[-1]
				else:
					res[i] = suf[-1]
			suf.append(i)
		return res


class Solution:

	def nearestSmallestTower(self, a):
		n = len(a)
		st = []
		ans = [-1] * n
		for i in range(n - 1, -1, -1):
			while len(st) and a[st[-1]] >= a[i]:
				st.pop()
			if len(st):
				ans[i] = st[-1]
			else:
				ans[i] = -1
			st.append(i)
		while len(st):
			st.pop()
		for i in range(n):
			while len(st) and a[st[-1]] >= a[i]:
				st.pop()
			if len(st):
				if ans[i] == -1:
					ans[i] = st[-1]
				else:
					index = st[-1]
					if i - index < ans[i] - i:
						ans[i] = index
					elif i - index == ans[i] - i:
						if a[index] <= a[ans[i]]:
							ans[i] = index
			st.append(i)
		return ans


class Solution:

	def left(self, arr):
		ans = [-1] * len(arr)
		stck = []
		for i in range(len(arr)):
			while stck and arr[stck[-1]] >= arr[i]:
				stck.pop()
			if stck:
				ans[i] = stck[-1]
			stck.append(i)
		return ans

	def right(self, arr):
		ans = [-1] * len(arr)
		stck = []
		for i in range(len(arr) - 1, -1, -1):
			while stck and arr[stck[-1]] >= arr[i]:
				stck.pop()
			if stck:
				ans[i] = stck[-1]
			stck.append(i)
		return ans

	def nearestSmallestTower(self, arr):
		left = self.left(arr)
		right = self.right(arr)
		ans = [-1] * len(arr)
		for i in range(len(arr)):
			leftdist = float('inf') if left[i] == -1 else i - left[i]
			rightdist = float('inf') if right[i] == -1 else right[i] - i
			if leftdist < rightdist or (leftdist == rightdist and left[i] != -1 and (arr[left[i]] <= arr[right[i]])):
				ans[i] = left[i]
			elif leftdist > rightdist or (leftdist == rightdist and right[i] != -1 and (arr[right[i]] <= arr[left[i]])):
				ans[i] = right[i]
			else:
				ans[i] = -1
		return ans


class Solution:

	def nearestSmallestTower(self, arr):
		s = []
		n = len(arr)
		ans = []
		for i in range(n):
			if not s:
				s.append((i, arr[i]))
				ans.append((-1, -1))
			elif s[-1][1] < arr[i]:
				ans.append(s[-1])
				s.append((i, arr[i]))
			else:
				while s and s[-1][1] >= arr[i]:
					s.pop()
				if s:
					ans.append(s[-1])
				else:
					ans.append((-1, -1))
				s.append((i, arr[i]))
		s = []
		for i in range(n - 1, -1, -1):
			if not s:
				s.append((i, arr[i]))
			elif s[-1][1] < arr[i]:
				t = s[-1]
				if ans[i][0] == -1:
					ans[i] = t
				elif abs(i - ans[i][0]) > abs(i - t[0]):
					ans[i] = t
				elif abs(i - ans[i][0]) == abs(i - t[0]) and ans[i][1] > t[1]:
					ans[i] = t
				s.append((i, arr[i]))
			else:
				while s and s[-1][1] >= arr[i]:
					s.pop()
				if s:
					t = s[-1]
					if ans[i][0] == -1:
						ans[i] = t
					elif abs(i - ans[i][0]) > abs(i - t[0]):
						ans[i] = t
					elif abs(i - ans[i][0]) == abs(i - t[0]) and ans[i][1] > t[1]:
						ans[i] = t
					s.append((i, arr[i]))
				s.append((i, arr[i]))
		finalAns = []
		for t in ans:
			finalAns.append(t[0])
		return finalAns