Given a circular interger array arr of size N (i.e ., the next element of arr [N-1] is arr[0] ), return the next greater number for every element in arr.
The next greater element of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number.
 
Example 1:
Input:
N = 3
arr[ ] = {1, 2, 1}
Output: {2, -1, 2}
Explanation: The first 1's next greater number is 2:
The number 2 can't find next greater number.
The second 1's next greater number needs to search circularly, which is also 2.
Example 2:
Input:
N = 5
arr[ ] = {5, 4, 3, 2, 1}
Output: {-1, 5, 5, 5, 5}
Your Task:
You don't need to read input or print anything. Your task is to complete the function nextGreaterElement() which takes the array of integers arr and N as parameters and returns an array of integer which contains the next greater number for every element in arr.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{4}
10^{-9 }≤ arr_{i  }≤ 10^{-9}

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def nextGreaterElement(self, N, arr):

        # Code here

Solutions:
class Solution:

	def nextGreaterElement(self, N, arr):
		ans = [-2] * N
		ma = max(arr)
		for i in range(N):
			if arr[i] == ma:
				ans[i] = -1
				pos = i
		stack = [ma]
		for i in range(N - 1, -1, -1):
			j = (i + pos) % N
			if ans[j] == -1:
				stack[:] = [ma]
			else:
				while stack[-1] <= arr[j]:
					stack.pop()
				ans[j] = stack[-1]
				stack.append(arr[j])
		return ans


class Solution:

	def nextGreaterElement(self, N, arr):
		maxpos = 0
		for i in range(1, N):
			if arr[i] > arr[maxpos]:
				maxpos = i
		stack = [arr[maxpos]]
		res = [-1 for _ in range(N)]
		i = maxpos - 1
		if i < 0:
			i += N
		while i != maxpos:
			while len(stack) != 0 and stack[-1] <= arr[i]:
				stack.pop()
			if len(stack) != 0:
				res[i] = stack[-1]
			stack.append(arr[i])
			i -= 1
			if i < 0:
				i += N
		return res


class Solution:

	def nextGreaterElement(self, N, arr):
		stack = []
		ans = [-1] * N
		stack.append(0)
		for i in range(1, N * 2):
			if len(stack) != 0:
				while arr[i % N] > arr[stack[-1] % N]:
					ans[stack[-1] % N] = arr[i % N]
					stack.pop()
					if len(stack) == 0:
						break
				stack.append(i % N)
			else:
				stack.append(i % N)
		return ans


class Solution:

	def nextGreaterElement(self, N, arr):
		s = []
		res = []
		for i in range(N - 1, -1, -1):
			s.append(arr[i])
		for i in range(N - 1, -1, -1):
			if arr[i] < s[-1]:
				res.append(s[-1])
			else:
				while len(s) != 0 and arr[i] >= s[-1]:
					s.pop()
				if len(s) == 0:
					res.append(-1)
				else:
					res.append(s[-1])
			s.append(arr[i])
		return res[::-1]


class Solution:

	def nextGreaterElement(self, N, arr):
		answer = []
		for i in range(N):
			flag = False
			for j in range(i + 1, N):
				if arr[j] > arr[i]:
					answer.append(arr[j])
					flag = True
					break
			if flag == False:
				for j in range(0, i):
					if arr[j] > arr[i]:
						answer.append(arr[j])
						flag = True
						break
			if flag == False:
				answer.append(-1)
		return answer


class Solution:

	def nextGreaterElement(self, N, arr):
		nge = [-1] * N
		s = []
		for i in range(2 * N - 1, -1, -1):
			while s and s[-1] <= arr[i % N]:
				s.pop()
			if i < N:
				if s:
					nge[i] = s[-1]
			s.append(arr[i % N])
		return nge


class Solution:

	def nextGreaterElement(self, N, nums):
		n = len(nums)
		result = []
		st = []
		for i in range(2 * n - 1, -1, -1):
			while len(st) > 0 and st[-1] <= nums[i % n]:
				st.pop()
			if i <= n - 1:
				if len(st) == 0:
					result.append(-1)
				else:
					result.append(st[-1])
			st.append(nums[i % n])
		return result[::-1]


class Solution:

	def nextGreaterElement(self, N, arr):
		stack = [arr[-1]]
		for i in range(N - 2, -1, -1):
			num = arr[i]
			while stack:
				if num > stack[-1]:
					stack.pop()
				else:
					break
			stack.append(num)
		ng = [-1] * N
		for i in range(N - 1, -1, -1):
			num = arr[i]
			while stack:
				if stack[-1] <= num:
					stack.pop()
				else:
					ng[i] = stack[-1]
					break
			stack.append(num)
		return ng


class Solution:

	def nextGreaterElement(self, n, arr):
		for i in range(n - 1):
			arr.append(arr[i])
		ans = []
		stack = [arr[n - 1]]
		for i in range(n - 1, -1, -1):
			if i == n - 1:
				flag = 0
				for j in range(i + 1, len(arr)):
					if arr[j] > arr[i]:
						stack.insert(0, arr[j])
						flag = 1
						ans.append(arr[j])
						break
				if flag == 1:
					continue
				else:
					ans.append(-1)
					stack.append(arr[i])
					continue
			if arr[i] >= stack[len(stack) - 1]:
				while len(stack) > 0 and arr[i] >= stack[len(stack) - 1]:
					stack.pop()
				if len(stack) == 0:
					flag = 0
					for j in range(i + 1, len(arr)):
						if arr[j] > arr[i]:
							ans.append(arr[j])
							flag = 1
							stack.append(arr[j])
							stack.append(arr[i])
							break
					if flag == 0:
						ans.append(-1)
						stack.append(arr[i])
				else:
					ans.append(stack[len(stack) - 1])
					stack.append(arr[i])
			elif arr[i] < stack[len(stack) - 1]:
				ans.append(stack[len(stack) - 1])
				stack.append(arr[i])
		return ans[::-1]


class Solution:

	def nextGreaterElement(self, n, arr):
		stack = []
		nge = [0] * n
		for i in range(2 * n - 1, -1, -1):
			while len(stack) != 0 and arr[i % n] >= stack[-1]:
				stack.pop()
			if len(stack) == 0:
				nge[i % n] = -1
			else:
				nge[i % n] = stack[-1]
			stack.append(arr[i % n])
		return nge


from collections import deque

class Solution:

	def nextGreaterElement(self, N, arr):
		arr.extend(arr)
		stack = deque()
		answer = []
		for i in range(2 * N - 1, -1, -1):
			while stack and (not stack[-1] > arr[i]):
				stack.pop()
			if not stack:
				answer.append(-1)
				stack.append(arr[i])
			else:
				answer.append(stack[-1])
				stack.append(arr[i])
		return answer[N:][::-1]


from collections import deque

class Solution:

	def nextGreaterElement(self, n, nums):
		st = []
		ans = [-1] * n
		for i in range(2 * n - 1, -1, -1):
			while st and nums[i % n] >= st[-1]:
				st.pop()
			if st and i < n:
				ans[i] = st[-1]
			st.append(nums[i % n])
		return ans


class Solution:

	def nextGreaterElement(self, N, arr):
		st = arr[::-1]
		l = []
		i = N - 1
		while i >= 0:
			if len(st) == 0:
				l.append(-1)
				st.append(arr[i])
				i -= 1
			elif st[-1] > arr[i]:
				l.append(st[-1])
				st.append(arr[i])
				i -= 1
			else:
				while st and st[-1] <= arr[i]:
					st.pop(-1)
		return l[::-1]


class Solution:

	def nextGreaterElement(self, n, arr):
		ans = [-1] * n
		stack = []
		for i in reversed(range(2 * n)):
			while stack and stack[-1] <= arr[i % n]:
				stack.pop()
			if i < n:
				if not stack:
					ans[i] = -1
				else:
					ans[i] = stack[-1]
			stack.append(arr[i % n])
		return ans


class Solution:

	def nextGreaterElement(self, N, arr):
		nums = arr
		n = len(nums)
		s = []
		ans = [0] * n
		for i in range(2 * n - 1, -1, -1):
			while s and s[-1] <= nums[i % n]:
				s.pop()
			if i < n:
				if s:
					ans[i] = s[-1]
				else:
					ans[i] = -1
			s.append(nums[i % n])
		return ans


class Solution:

	def nextGreaterElement(self, n, arr):
		res = [-1] * n
		stack = []
		for i in range(2 * n - 1, -1, -1):
			while stack and arr[i % n] >= stack[-1]:
				stack.pop()
			if i < n:
				if stack:
					res[i] = stack[-1]
			stack.append(arr[i % n])
		return res


class Solution:

	def nextGreaterElement(self, N, arr):
		stack = []
		nge = [-1] * N
		i = 2 * N - 1
		while i >= 0:
			while stack and stack[-1] <= arr[i % N]:
				stack.pop()
			if i < N:
				if stack:
					nge[i] = stack[-1]
			stack.append(arr[i % N])
			i -= 1
		return nge


class Solution:

	def nextGreaterElement(self, N, arr):
		(prev, idx) = (0, 0)
		ans = [-1 for j in range(N)]
		while prev < N:
			if prev != N - 1 and ans[prev] == -1:
				for idx in range(prev + 1, N):
					if arr[idx] > arr[prev]:
						ans[prev] = arr[idx]
						break
			if prev != 0 and ans[prev] == -1:
				for idx in range(0, prev):
					if arr[idx] > arr[prev]:
						ans[prev] = arr[idx]
						break
			prev += 1
		return ans


class Solution:

	def nextGreaterElement(self, N, arr):
		nextGreatElements = [-1 for _ in range(len(arr))]
		stack = []
		for idx in range(len(arr) - 1, -1, -1):
			while len(stack) != 0 and arr[idx] >= stack[-1]:
				stack.pop()
			nextGreatElements[idx] = -1 if len(stack) == 0 else stack[-1]
			stack.append(arr[idx])
		for idx in range(len(arr) - 1, -1, -1):
			while len(stack) != 0 and arr[idx] >= stack[-1]:
				stack.pop()
			nextGreatElements[idx] = -1 if len(stack) == 0 else stack[-1]
			stack.append(arr[idx])
		return nextGreatElements


class Solution:

	def nextGreaterElement(self, N, arr):
		res = [-1 for i in range(N)]
		stack = [arr[-1]]
		for j in range(2, 0, -1):
			for i in range(N - j, -1, -1):
				while stack and stack[-1] <= arr[i]:
					stack.pop()
				if stack and res[i] == -1:
					res[i] = stack[-1]
				stack.append(arr[i])
		return res


class Solution:

	def nextGreaterElement(self, n, arr):
		s = []
		ans = [0] * n
		boo = False
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[n - 1]:
				s.append(arr[i])
				boo = True
		if not boo:
			s.append(-1)
		for i in range(n - 1, -1, -1):
			while len(s) > 0 and arr[i] >= s[-1]:
				s.pop()
			if not s:
				ans[i] = -1
				s.append(arr[i])
				continue
			ans[i] = s[-1]
			s.append(arr[i])
		return ans


class Solution:

	def nextGreaterElement(self, N, arr):
		arr = arr + arr
		i = 0
		stack = []
		ans = [-1 for x in arr]
		while i < 2 * N:
			if stack == []:
				stack.append(i)
				i += 1
			elif arr[stack[-1]] >= arr[i]:
				stack.append(i)
				i += 1
			elif arr[stack[-1]] < arr[i]:
				while stack and arr[stack[-1]] < arr[i]:
					x = stack[-1]
					y = arr[i]
					ans[x] = y
					stack.pop()
				stack.append(i)
				i += 1
		return ans[:N]


class Solution:

	def nextGreaterElement(self, N, arr):
		s = arr[::-1]
		l = N
		ans = []
		i = 0
		for r in range(N - 1, -1, -1):
			while l > 0 and s[-1] <= arr[r]:
				l -= 1
				s.pop()
			if l > 0:
				ans += [s[-1]]
			else:
				ans += [-1]
			s += [arr[r]]
			l += 1
		return ans[::-1]


class Solution:

	def nextGreaterElement(self, N, arr):
		res = [-1 for _ in range(N)]
		st = []
		for i in range(2 * N - 1, -1, -1):
			while st and st[-1] <= arr[i % N]:
				st.pop()
			if i < N:
				if st:
					res[i] = st[-1]
			st.append(arr[i % N])
		return res


class Solution:

	def nextGreaterElement(self, n, arr):
		n = len(arr)
		nge = [-1] * n
		st = []
		for i in range(2 * n - 1, -1, -1):
			while st and st[-1] <= arr[i % n]:
				st.pop()
			if i < n:
				if st:
					nge[i] = st[-1]
			st.append(arr[i % n])
		return nge


from collections import deque

class Solution:

	def nextGreaterElement(self, n, arr):
		stack = deque()
		list1 = [-1] * n
		for j in range(2 * n - 1, -1, -1):
			while len(stack) and stack[-1] <= arr[j % n]:
				stack.pop()
			if j < n:
				if len(stack):
					list1[j] = stack[-1]
				else:
					list1[j] = -1
			stack.append(arr[j % n])
		return list1


class Solution:

	def nextGreaterElement(self, N, arr):
		stack = []
		ans = [None for _ in range(len(arr))]
		n = len(arr)
		for i in range(2 * n - 1, -1, -1):
			while len(stack) and stack[-1] <= arr[i % n]:
				stack.pop()
			if i % n < n:
				if len(stack):
					ans[i % n] = stack[-1]
				else:
					ans[i % n] = -1
			stack.append(arr[i % n])
		return ans


class Solution:

	def nextGreaterElement(self, N, nums):
		l = len(nums)
		nums = nums * 2

		def nextgreater(st, num):
			while len(st) and st[-1] <= num:
				st.pop()
			st.append(num)
			return -1 if len(st) <= 1 else st[-2]
		st = []
		ans = []
		for i in range(len(nums) - 1, -1, -1):
			ans.append(nextgreater(st, nums[i]))
		ans = ans[::-1]
		return ans[:l]


class Solution:

	def nextGreaterElement(self, N, arr):
		a = []
		arr2 = arr * 2
		r = [-1] * len(arr2)
		for i in range(len(arr2)):
			while a and arr2[a[-1]] < arr2[i]:
				r[a.pop()] = arr2[i]
			a.append(i)
		return r[:N]


class Solution:

	def nextGreaterElement(self, N, arr):
		stack = []
		arr = arr + arr
		result = [-1] * N
		for i in range(2 * N - 1, -1, -1):
			while stack and arr[stack[-1]] <= arr[i % N]:
				stack.pop()
			if stack:
				result[i % N] = arr[stack[-1]]
			stack.append(i % N)
		return result


class Solution:

	def nextGreaterElement(self, N, arr):
		ans = [-1 for i in range(N)]
		stack = []
		for _ in range(2):
			for j in range(N - 1, -1, -1):
				v = arr[j]
				while stack and v >= stack[-1]:
					stack.pop()
				if stack:
					ans[j] = stack[-1]
				stack.append(v)
		return ans


class Stack:

	def __init__(self):
		self.st = []

	def pop(self):
		if len(self.st) == 0:
			return -1
		return self.st.pop()

	def push(self, ele):
		self.st.append(ele)

	def peek(self):
		if len(self.st) == 0:
			return -1
		return self.st[-1]

class Solution:

	def __init__(self):
		self.s = Stack()

	def nextGreaterElement(self, N, arr):
		L = arr[::-1]
		A = []
		for i in range(0, 2 * N):
			i = i % N
			while L[i] >= self.s.peek() and self.s.peek() != -1:
				self.s.pop()
			A.append(self.s.peek())
			self.s.push(L[i])
		return A[-1:-(N + 1):-1]


class Solution:

	def nextGreaterElement(self, N, arr):
		new = []
		for i in range(N):
			new.append((arr[i], i))
		new = new + new
		stack = []
		ans = []
		for i in range(len(new) - 1, -1, -1):
			if not stack:
				stack.append(new[i])
			else:
				(cur, idx) = new[i]
				while stack and stack[-1][0] <= cur:
					stack.pop()
				if not stack or (stack and stack[-1][1] == idx):
					ans.append(-1)
				else:
					ans.append(stack[-1][0])
				stack.append(new[i])
		ans = ans[::-1]
		ans = ans[:N]
		return ans


class Solution:

	def nextGreaterElement(self, N, nums):
		n = N
		stack = []
		ans = [-1] * n
		i = 2 * n - 1
		while i >= 0:
			while stack and stack[-1] <= nums[i % n]:
				stack.pop()
			if len(stack) != 0:
				ans[i % n] = stack[-1]
			stack.append(nums[i % n])
			i -= 1
		return ans


class Solution:

	def nextGreaterElement(self, N, arr):
		stack = []
		nge = [0] * N
		for i in range(N - 1, -1, -1):
			while stack and stack[-1] <= arr[i]:
				stack.pop(-1)
			stack.append(arr[i])
		for i in range(N - 1, -1, -1):
			while stack and stack[-1] <= arr[i]:
				stack.pop(-1)
			if stack:
				nge[i] = stack[-1]
			else:
				nge[i] = -1
			stack.append(arr[i])
		return nge


class Solution:

	def nextGreaterElement(self, n, arr):
		stack = []
		n = len(arr)
		res = [0] * n
		i = 2 * len(arr) - 1
		while i >= 0:
			if not stack:
				res[i % n] = -1
			elif stack[-1] > arr[i % n]:
				res[i % n] = stack[-1]
			elif stack[-1] <= arr[i % n]:
				stack.pop()
				continue
			stack.append(arr[i % n])
			i -= 1
		return res


class Solution:

	def nextGreaterElement(self, N, arr):
		st = []
		res = []
		arr = arr[::-1]
		arr += arr
		for i in arr:
			if not st:
				res.append(-1)
				st.append(i)
			else:
				while st and i >= st[-1]:
					st.pop()
				if st:
					res.append(st[-1])
					st.append(i)
				else:
					res.append(-1)
					st.append(i)
		res = res[::-1]
		return res[:N]


class Solution:

	def nextGreaterElement(self, N, arr):
		new_arr = []
		new_arr.extend(arr)
		new_arr.extend(arr)
		nge_arr = [0 for i in range(len(new_arr))]
		stack = []
		for i in reversed(range(len(new_arr))):
			if len(stack) == 0:
				nge_arr[i] = -1
				stack.append(new_arr[i])
			else:
				if new_arr[i] < stack[-1]:
					nge_arr[i] = stack[-1]
				else:
					while len(stack) > 0 and stack[-1] <= new_arr[i]:
						stack.pop()
					if len(stack) == 0:
						nge_arr[i] = -1
					else:
						nge_arr[i] = stack[-1]
				stack.append(new_arr[i])
		return nge_arr[:len(arr)]


class Solution:

	def nextGreaterElement(self, N, nums):
		t = len(nums)
		l = []
		for i in range(t):
			for j in range(i + 1, i + t):
				if nums[j % t] > nums[i]:
					l.append(nums[j % t])
					break
			else:
				l.append(-1)
		return l


class Solution:

	def nextGreaterElement(self, n, nums):
		n = len(nums)
		stk = []
		out = []
		for i in range(2 * n - 1, -1, -1):
			curr = nums[i % n]
			while len(stk) != 0 and stk[-1] <= curr:
				stk.pop()
			if len(stk) == 0:
				out.append(-1)
			else:
				out.append(stk[-1])
			stk.append(curr)
		k = out[::-1]
		return k[0:n]


class Solution:

	def nextGreaterElement(self, n, arr):
		s = arr[::-1]
		ans = [0] * n
		i = n - 1
		while i >= 0:
			if len(s) == 0:
				ans[i] = -1
				s.append(arr[i])
				i -= 1
			elif s[-1] > arr[i]:
				ans[i] = s[-1]
				s.append(arr[i])
				i -= 1
			else:
				while len(s) and s[-1] <= arr[i]:
					s.pop()
		return ans


class Solution:

	def nextGreaterElement(self, n, nums):
		stack = nums[::-1]
		stack.pop(0)
		ans = []
		for i in range(len(nums) - 1, -1, -1):
			if len(stack) == 0:
				ans.append(-1)
				stack.append(nums[i])
			else:
				flag = 0
				while len(stack) != 0:
					if stack[-1] > nums[i]:
						ans.append(stack[-1])
						stack.append(nums[i])
						flag = 1
						break
					else:
						stack.pop(len(stack) - 1)
				if flag == 0:
					ans.append(-1)
					stack.append(nums[i])
		return ans[::-1]


from collections import deque

class Solution:

	def nextGreaterElement(self, N, arr):
		NGE = deque()
		ans = []
		for i in range(len(arr) - 1, -1, -1):
			NGE.append(arr[i])
		for i in range(len(arr) - 1, -1, -1):
			if len(NGE) > 0 and NGE[-1] > arr[i]:
				ans.append(NGE[-1])
			elif len(NGE) > 0 and NGE[-1] <= arr[i]:
				while len(NGE) > 0 and NGE[-1] <= arr[i]:
					NGE.pop()
				if len(NGE) == 0:
					ans.append(-1)
				else:
					ans.append(NGE[-1])
			NGE.append(arr[i])
		ans.reverse()
		return ans


class Solution:

	def nextGreaterElement(self, N, arr):
		new = arr[0:N] + arr[0:N]
		st = []
		ans = []
		i = len(new) - 1
		while i >= 0:
			if len(st) == 0:
				st.append(new[i])
				ans.append(-1)
			else:
				while len(st) != 0 and st[-1] <= new[i]:
					st.pop()
				if len(st) != 0:
					ans.append(st[-1])
				else:
					ans.append(-1)
				st.append(new[i])
			i -= 1
		return ans[N:][::-1]


class Solution:

	def nextGreaterElement(self, N, arr):
		arr += arr
		stck = []
		answer = [-1] * (N * 2)
		for (ind, val) in enumerate(arr):
			while stck and arr[stck[-1]] < arr[ind]:
				temp = stck.pop()
				answer[temp] = arr[ind]
			else:
				stck.append(ind)
		return answer[:N]


class Solution:

	def nextGreaterElement(self, n, arr):
		arr = [*arr, *arr]
		stack = list()
		ans = []
		for x in arr[::-1]:
			if not stack:
				ans.append(-1)
			else:
				while stack:
					if stack[-1] > x:
						break
					stack.pop()
				if not stack:
					ans.append(-1)
				else:
					ans.append(stack[-1])
			stack.append(x)
		return ans[::-1][:n]


class Solution:

	def nextGreaterElement(self, N, a):
		x = len(a)
		st = []
		ans = []
		for i in range(2 * x - 1, -1, -1):
			while len(st) != 0 and st[-1] <= a[i % x]:
				st.pop()
			if len(st) == 0:
				ans.append(-1)
			else:
				ans.append(st[-1])
			st.append(a[i % x])
		ans.reverse()
		return ans[:x]


class Solution:

	def nextGreaterElement(self, N, arr):
		stack = arr[::-1]
		ans = []
		for i in range(N - 1, -1, -1):
			if len(stack) == 0:
				ans.append(-1)
			elif len(stack) > 0 and stack[-1] > arr[i]:
				ans.append(stack[-1])
			elif len(stack) > 0 and stack[-1] <= arr[i]:
				while len(stack) > 0 and stack[-1] <= arr[i]:
					stack.pop()
				if len(stack) == 0:
					ans.append(-1)
				else:
					ans.append(stack[-1])
			stack.append(arr[i])
		return ans[::-1]


class Solution:

	def nextGreaterElement(self, N, arr):
		st = []
		nge = []
		l = len(arr)
		for g in range(2 * l - 1, -1, -1):
			if len(st) == 0:
				st.append(arr[g % l])
			else:
				while len(st) != 0 and st[-1] <= arr[g % l]:
					st.pop()
				if g < l:
					if len(st) == 0:
						nge.append(-1)
					else:
						nge.append(st[-1])
				st.append(arr[g % l])
		return nge[::-1]


class Solution:

	def nextGreaterElement(self, N, arr):
		ans = []
		stk = []
		for i in range(2 * N - 1, -1, -1):
			while stk and stk[-1] <= arr[i % N]:
				stk.pop()
			if i < N:
				if stk:
					ans.append(stk[-1])
				else:
					ans.append(-1)
			stk.append(arr[i % N])
		return ans[::-1]


class Solution:

	def nextGreaterElement(self, N, arr):
		ans = [-1 for i in range(N)]
		s = []
		for i in range(N):
			while len(s) > 0 and s[-1][0] < arr[i]:
				item = s.pop()
				ans[item[1]] = arr[i]
			s.append([arr[i], i])
		for i in range(N):
			while len(s) > 0 and s[-1][0] < arr[i]:
				item = s.pop()
				ans[item[1]] = arr[i]
		return ans