Given postorder traversal of a Binary Search Tree, you need to construct a BST from postorder traversal. The output will be inorder traversal of the constructed BST.
 
Example 1:
Input:
6
1 7 5 50 40 10
Output:
1 5 7 10 40 50
Explanation:
Testcase 1: The BST for the given post order traversal is:
Thus the inorder traversal of BST is: 1 5 7 10 40 50.
 
Your Task:
The task is to complete the function constructTree() which takes an array post[], size as as the argument and returns the root of BST. 
 
Expected Time Complexity: O(No. of  nodes in BST)
Expected Auxiliary Space: O(No. of  nodes in BST)
 
Constraints:
1 <= T <= 100
1 <= N <= 200

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Range queries

Starter code: #User function Template for python3



class Solution:

    def constructTree(self,post,n):

        # code here



Solutions:
class Solution:

	def constructTree(self, post, n):
		if post:
			node_val = post.pop()
			root = Node(node_val)
			i = len(post) - 1
			while i >= 0:
				if post[i] > node_val:
					i -= 1
				else:
					break
			root.right = self.constructTree(post[i + 1:], n)
			root.left = self.constructTree(post[:i + 1], n)
			return root


class Solution:

	def constructTree(self, post, n):

		def helper(post, low, high):
			nonlocal index
			if index < 0:
				return
			if low > high:
				return
			if post[index] < low or post[index] > high:
				return
			x = post[index]
			root = Node(post[index])
			index -= 1
			root.right = helper(post, x + 1, high)
			root.left = helper(post, low, x - 1)
			return root
		index = n - 1
		min = -2 ** 31
		max = 2 ** 31
		return helper(post, min, max)


class Solution:

	def constructTree(self, post, n):
		post.sort()

		def sortedArrayToBST(nums, start, last):
			if start > last:
				return
			mid = (start + last) // 2
			root = Node(nums[mid])
			root.left = sortedArrayToBST(nums, start, mid - 1)
			root.right = sortedArrayToBST(nums, mid + 1, last)
			return root
		return sortedArrayToBST(post, 0, n - 1)


class Solution:

	def constructTree(self, post, n):
		post.sort()
		return self.helper(post)

	def helper(self, arr):
		if not arr:
			return
		mid = len(arr) // 2
		root = Node(arr[mid])
		root.left = self.helper(arr[:mid])
		root.right = self.helper(arr[mid + 1:])
		return root


class Solution:

	def constructTree(self, post, n):
		if len(post) == 0:
			return None
		stack = []
		node = Node(post[-1])
		nodeCopy = node
		stack.append(node)
		for i in range(n - 2, -1, -1):
			newNode = Node(post[i])
			if stack[-1].val < post[i]:
				stack[-1].right = newNode
			else:
				topNode = stack[-1]
				while len(stack) and stack[-1].val > post[i]:
					topNode = stack.pop()
				topNode.left = newNode
			stack.append(newNode)
		return nodeCopy


import math

class Solution:

	def constructTree(self, post, n):
		self.i = n - 1

		def helper(post, lb, ub):
			if self.i < 0 or post[self.i] >= ub or post[self.i] <= lb:
				return None
			root = Node(post[self.i])
			self.i -= 1
			root.right = helper(post, root.val, ub)
			root.left = helper(post, lb, root.val)
			return root
		return helper(post, -math.inf, math.inf)


class Solution:

	def find(post, start, end):
		if start > end:
			return
		mid = (start + end) // 2
		root = Node(post[mid])
		root.right = Solution.find(post, mid + 1, end)
		root.left = Solution.find(post, start, mid - 1)
		return root

	def constructTree(self, post, n):
		post.sort()
		return Solution.find(post, 0, n - 1)


class Solution:

	def find(post, start, end):
		if start > end:
			return
		root = Node(post[end])
		i = end
		if root is None:
			return None
		while i >= 0:
			if post[i] < root.val:
				break
			i = i - 1
		root.right = Solution.find(post, i + 1, end - 1)
		root.left = Solution.find(post, start, i)
		return root

	def constructTree(self, post, n):
		return Solution.find(post, 0, n - 1)


class Solution:

	def constructTree(self, postorder, n):
		n = len(postorder)

		def tempfunc(lpo, rpo):
			nonlocal n, postorder
			if lpo > rpo:
				return None
			if lpo == rpo:
				return Node(postorder[lpo - 1])
			k = lpo
			while lpo <= n and postorder[k - 1] < postorder[rpo - 1]:
				k += 1
			left = tempfunc(lpo, k - 1)
			right = tempfunc(k, rpo - 1)
			new = Node(postorder[rpo - 1])
			new.left = left
			new.right = right
			return new
		return tempfunc(1, n)


from bisect import bisect_left

class Solution:

	def constructTree(self, post, n):
		root = Node(0)
		return self.helper(root, post)

	def helper(self, root, post):
		root.val = post.pop()
		n = bisect_left(post, root.val)
		post1 = post[:n]
		post2 = post[n:]
		if post1:
			root.left = Node(0)
			self.helper(root.left, post1)
		if post2:
			root.right = Node(0)
			self.helper(root.right, post2)
		return root


class Solution:

	def constructTreeUtil(self, post, key, min, max, size):
		if self.postIndex < 0:
			return None
		root = None
		if key > min and key < max:
			root = Node(key)
			self.postIndex -= 1
			if self.postIndex >= 0:
				root.right = self.constructTreeUtil(post, post[self.postIndex], key, max, size)
				root.left = self.constructTreeUtil(post, post[self.postIndex], min, key, size)
		return root

	def constructTree(self, post, n):
		self.postIndex = n - 1
		return self.constructTreeUtil(post, post[self.postIndex], -2 * 10 ** 31, 2 * 10 ** 31, n)


class Solution:

	def getBST(self, arr):
		if not arr:
			return
		mid = len(arr) // 2
		node = Node(arr[mid])
		node.left = self.getBST(arr[:mid])
		node.right = self.getBST(arr[mid + 1:])
		return node

	def constructTree(self, post, n):
		post.sort()
		return self.getBST(post)


class Solution:

	def constructTree(self, post, n):
		n = len(post)
		root = Node(post[-1])
		stack = [root]
		for i in range(n - 2, -1, -1):
			num = post[i]
			node = Node(num)
			if num > stack[-1].val:
				stack[-1].right = node
			else:
				while stack and num < stack[-1].val:
					last = stack.pop()
				last.left = node
			stack.append(node)
		return root


class Solution:

	def constructTree(self, post, n):

		def making(post, start, end):
			if start > end:
				return None
			temp = Node(post[end])
			i = end
			while i >= start:
				if post[i] < temp.val:
					break
				i -= 1
			temp.right = making(post, i + 1, end - 1)
			temp.left = making(post, start, i)
			return temp
		return making(post, 0, n - 1)


class Solution:

	def __init__(self):
		self.i = 0

	def constructTree(self, post, n):
		self.i = n
		return self.solve(post, float('-inf'), float('inf'))

	def solve(self, l, mi, ma):
		if self.i == 0:
			return None
		if l[self.i - 1] > mi and l[self.i - 1] < ma:
			r = Node(l[self.i - 1])
			self.i -= 1
			r.right = self.solve(l, l[self.i], ma)
			r.left = self.solve(l, mi, l[self.i])
			return r
		else:
			return None


class Solution:

	def insert(self, root, val):
		if root is None:
			return Node(val)
		if val > root.val:
			root.right = self.insert(root.right, val)
		else:
			root.left = self.insert(root.left, val)
		return root

	def constructTree(self, post, n):
		post = post[::-1]
		root = Node(post[0])
		for i in post[1:]:
			root = self.insert(root, i)
		return root


class Solution:

	def convertBST(self, post, left, right):
		if left > right:
			return
		mid = (left + right) // 2
		node = Node(post[mid])
		node.left = self.convertBST(post, left, mid - 1)
		node.right = self.convertBST(post, mid + 1, right)
		return node

	def constructTree(self, post, n):
		post.sort()
		return self.convertBST(post, 0, n - 1)


class Solution:

	def constructTree(self, post, n):

		def constructor(i, j):
			if j < i:
				return None
			root = Node(post[j])
			k = j - 1
			while k >= i and post[j] < post[k]:
				k -= 1
			root.right = constructor(k + 1, j - 1)
			root.left = constructor(i, k)
			return root
		return constructor(0, n - 1)


class Solution:

	def constructTree(self, post, n):
		_sorted_post = sorted(post)
		return self._build_tree(_sorted_post, 0, len(_sorted_post) - 1)

	def _build_tree(self, _sorted_post, low, high):
		if low > high:
			return None
		if (low + high) % 2 == 0:
			mid = (low + high) // 2
		else:
			mid = (low + high) // 2
			mid += 1
		root = Node(_sorted_post[mid])
		root.left = self._build_tree(_sorted_post, low, mid - 1)
		root.right = self._build_tree(_sorted_post, mid + 1, high)
		return root


class Solution:

	def constructTree(self, post, n):
		self.i = n - 1
		return self.solve(post, float('-inf'), float('inf'))

	def solve(self, post, mi, ma):
		if self.i == len(post):
			return None
		if post[self.i] <= mi or post[self.i] >= ma:
			return None
		root = Node(post[self.i])
		self.i -= 1
		root.right = self.solve(post, root.val, ma)
		root.left = self.solve(post, mi, root.val)
		return root


class Solution:

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

	def makePGE(self, n, postorder):
		pge = [-1] * n
		stack = []
		stack.append(n - 1)
		for i in range(n - 2, -1, -1):
			while stack != [] and postorder[i] < postorder[stack[-1]]:
				pge[stack[-1]] = i
				stack = stack[:-1]
			stack.append(i)
		self.PGE = pge
		return

	def make(self, postorder, i, j):
		if i > j:
			return None
		root = Node(postorder[j])
		root.left = self.make(postorder, i, self.PGE[j])
		root.right = self.make(postorder, self.PGE[j] + 1, j - 1)
		return root

	def constructTree(self, post, n):
		n = len(post)
		self.makePGE(n, post)
		return self.make(post, 0, n - 1)


class Solution:

	def createPse(self, postorder):
		stack = []
		n = len(postorder)
		pse = [-1] * n
		stack.append(n - 1)
		for i in range(n - 2, -1, -1):
			while len(stack) and postorder[i] < postorder[stack[len(stack) - 1]]:
				pse[stack[len(stack) - 1]] = i
				stack.pop()
			stack.append(i)
		return pse

	def construct(self, post, l, h):
		if l > h:
			return None
		root = Node(post[h])
		if l == h:
			return root
		m = self.pse[h]
		root.left = self.construct(post, l, m)
		root.right = self.construct(post, m + 1, h - 1)
		return root

	def constructTree(self, post, n):
		l = 0
		h = len(post) - 1
		self.pse = self.createPse(post)
		return self.construct(post, l, h)


class Solution:

	def constructTree(self, post, n):
		post.sort()
		l = []
		for i in post:
			l.append(Node(i))
		for i in range(n - 1):
			l[i].right = l[i + 1]
		return l[0]


class Solution:

	def constructTree(self, post, n):

		def makeBST(post, lb, ub):
			if self.i == len(post):
				return None
			if post[self.i] <= lb or post[self.i] >= ub:
				return None
			root = Node(post[self.i])
			self.i -= 1
			root.right = makeBST(post, root.val, ub)
			root.left = makeBST(post, lb, root.val)
			return root
		self.i = n - 1
		lb = -float('inf')
		ub = float('inf')
		return makeBST(post, lb, ub)


class Solution:

	def constructTree(self, post, n):
		post.sort()

		def dfs(post):
			if not post:
				return
			mid = len(post) // 2
			node = Node(post[mid])
			node.left = dfs(post[:mid])
			node.right = dfs(post[mid + 1:])
			return node
		root = dfs(post)
		return root


def constructTreeUtil(post, n):
	root = Node(post[n - 1])
	s = []
	s.append(root)
	i = n - 2
	while i >= 0:
		x = Node(post[i])
		temp = None
		while len(s) > 0 and post[i] < s[-1].val:
			temp = s[-1]
			s.pop()
		if temp != None:
			temp.left = x
		else:
			s[-1].right = x
		s.append(x)
		i = i - 1
	return root

class Solution:

	def constructTree(self, post, n):
		return constructTreeUtil(post, n)


class Solution:

	def constructTree(self, post, n):
		root = None
		for i in range(len(post) - 1, -1, -1):
			if root == None:
				root = Node(post[i])
			else:
				tail = None
				temp = root
				while temp:
					tail = temp
					if post[i] > temp.val:
						temp = temp.right
					else:
						temp = temp.left
				if post[i] > tail.val:
					tail.right = Node(post[i])
				else:
					tail.left = Node(post[i])
		return root


class Solution:

	def constructTree(self, post, n):
		post.sort()
		from math import inf

		def dfs(post):
			if not post:
				return
			mid = len(post) // 2
			node = Node(post[mid])
			node.left = dfs(post[:mid])
			node.right = dfs(post[mid + 1:])
			return node
		root = dfs(post)
		return root


class Solution:

	def construct(self, post, mn, mx, index):
		if index[0] < 0:
			return None
		if not (post[index[0]] > mn and post[index[0]] < mx):
			return None
		nd = Node(post[index[0]])
		index[0] -= 1
		nd.right = self.construct(post, nd.val, mx, index)
		nd.left = self.construct(post, mn, nd.val, index)
		return nd

	def constructTree(self, post, n):
		mn = -int(1000000000.0)
		mx = int(1000000000.0)
		index = [n - 1]
		return self.construct(post, mn, mx, index)


class Solution:

	def __init__(self):
		self.index = 0

	def constructTree(self, post, n):
		self.index = n - 1
		return self.rec(post, -1000000, 1000000)

	def rec(self, post, L, R):
		if self.index == -1:
			return None
		if post[self.index] > L and post[self.index] < R:
			node = Node(post[self.index])
			self.index -= 1
			node.right = self.rec(post, node.val, R)
			node.left = self.rec(post, L, node.val)
			return node
		else:
			return None


import sys

class Node:

	def __init__(self, val=0, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right

class Solution:

	def create(self, post, idx, low, high):
		if idx[0] < 0 or post[idx[0]] >= high or post[idx[0]] <= low:
			return None
		root = Node(post[idx[0]])
		idx[0] -= 1
		root.right = self.create(post, idx, root.val, high)
		root.left = self.create(post, idx, low, root.val)
		return root

	def constructTree(self, post, n):
		idx = [n - 1]
		return self.create(post, idx, -sys.maxsize, sys.maxsize)


class Solution:

	def constructTree(self, post, n):
		if len(post) == 0:
			return
		post.sort()
		for x in post:
			print(x, end=' ')


class Solution:

	def createBST(self, posOT, lowbond, highbond, index):
		if index[0] < 0 or lowbond > highbond or posOT[index[0]] < lowbond or (posOT[index[0]] > highbond):
			return None
		node = posOT[index[0]]
		root = Node(posOT[index[0]])
		index[0] -= 1
		root.right = self.createBST(posOT, node + 1, highbond, index)
		root.left = self.createBST(posOT, lowbond, node - 1, index)
		return root

	def constructTree(self, posOT, n):
		Min = -100 ** 9
		Max = 100 ** 9
		index = [n - 1]
		return self.createBST(posOT, Min, Max, index)


INT_MIN = -2 ** 31
INT_MAX = 2 ** 31

class Solution:

	def constructTree(self, post, n):
		postIndex = [n - 1]
		return self.constructTreeUtil(post, postIndex, post[postIndex[0]], INT_MIN, INT_MAX, n)

	def constructTreeUtil(self, post, postIndex, key, min, max, size):
		if postIndex[0] < 0:
			return None
		root = None
		if key > min and key < max:
			root = Node(key)
			postIndex[0] = postIndex[0] - 1
			if postIndex[0] >= 0:
				root.right = self.constructTreeUtil(post, postIndex, post[postIndex[0]], key, max, size)
				root.left = self.constructTreeUtil(post, postIndex, post[postIndex[0]], min, key, size)
		return root

	def InOrder(self, root):
		if root == None:
			return 0
		BinaryTree_list = []
		self.InorderHelper(root, BinaryTree_list)

	def InorderHelper(self, root, BinaryTree_list):
		if root == None:
			return 0
		self.InorderHelper(root.left, BinaryTree_list)
		BinaryTree_list.append(root.data)
		self.InorderHelper(root.right, BinaryTree_list)


class Solution:

	def constructTree(self, post, n):
		stack = []
		for pointer in range(n - 1, -1, -1):
			cur = Node(post[pointer])
			if pointer == n - 1:
				root = cur
			if not stack:
				stack.append(cur)
			elif cur.val > stack[-1].val:
				stack[-1].right = cur
				stack.append(cur)
			else:
				while stack and cur.val < stack[-1].val:
					par = stack.pop(-1)
				par.left = cur
				stack.append(cur)
		return root


class Solution:

	def constructTree(self, post, n):
		global pointer
		pointer = n - 1
		mini = float('-inf')
		maxi = float('inf')
		root = self.util(post, mini, maxi)
		return root

	def util(self, post, mini, maxi):
		global pointer
		if pointer < 0:
			return None
		if post[pointer] < mini or post[pointer] > maxi:
			return None
		cur = Node(post[pointer])
		pointer -= 1
		cur.right = self.util(post, cur.val, maxi)
		cur.left = self.util(post, mini, cur.val)
		return cur

	def inorder(self, root, ans):
		if root is None:
			return
		self.inorder(root.left, ans)
		ans.append(root.val)
		self.inorder(root.right, ans)


class Solution:

	def constructTreeUtil(self, postorder, mini, maxi):
		global idx
		if idx < 0:
			return None
		if postorder[idx] < mini or postorder[idx] > maxi:
			return None
		root = Node(postorder[idx])
		idx -= 1
		root.right = self.constructTreeUtil(postorder, root.val + 1, maxi)
		root.left = self.constructTreeUtil(postorder, mini, root.val - 1)
		return root

	def constructTree(self, postorder, n):
		global idx
		idx = n - 1
		return self.constructTreeUtil(postorder, float('-inf'), float('inf'))


class Solution:

	def arr_to_biin(self, arr):
		if not arr:
			return None
		ks = len(arr) // 2
		root = Node(arr[ks])
		root.left = self.arr_to_biin(arr[:ks])
		root.right = self.arr_to_biin(arr[ks + 1:])
		return root

	def constructTree(self, post, n):
		post.sort()
		return self.arr_to_biin(post)


import sys

class Solution:

	def __init__(self):
		self.n = 0

	def constructTree(self, post, n):
		post = post[::-1]
		self.n = n
		return self.build(post, [0], -1)

	def build(self, post, i, bound):
		if i[0] == self.n or post[i[0]] < bound:
			return None
		root = Node(post[i[0]])
		i[0] += 1
		root.right = self.build(post, i, root.val)
		root.left = self.build(post, i, bound)
		return root


import sys

class Solution:

	def constructTree(self, post, n):
		return self.build(post, 0, n - 1)

	def build(self, post, s, e):
		if s > e:
			return None
		root = Node(post[e])
		if s == e:
			return root
		ind = s
		while post[ind] < root.val:
			ind += 1
		root.left = self.build(post, s, ind - 1)
		root.right = self.build(post, ind, e - 1)
		return root


class Solution:

	def constructTree(self, post, n):
		p = post[:]
		post.sort()
		i = post
		x = self.create(p, i)
		return x

	def create(self, p, i):
		if not p or not i:
			return None
		mid = i.index(p[-1])
		root = Node(p[-1])
		root.left = self.create(p[0:mid], i[:mid])
		root.right = self.create(p[mid:len(p) - 1], i[mid + 1:])
		return root


class Solution:

	def constructTree(self, post, n):
		return self.util(post, 0, n - 1)

	def util(self, post, x, y):
		if x > y:
			return None
		if x == y:
			return Node(post[x])
		root = Node(post[y])
		index = -1
		for i in range(y - 1, x - 1, -1):
			if post[i] < post[y]:
				index = i
				break
		root.left = self.util(post, x, index)
		if index == -1 and x != 0:
			index = x - 1
		root.right = self.util(post, index + 1, y - 1)
		return root


class Solution:

	def constructTree(self, post, n):
		if n == 0:
			return None
		if n == 1:
			return Node(post[0])
		root = Node(post[-1])
		i = n - 2
		while i >= 0 and post[i] > root.val:
			i -= 1
		left = post[:i + 1]
		root.left = self.constructTree(left, len(left))
		right = post[i + 1:-1]
		root.right = self.constructTree(right, len(right))
		return root

class Node:

	def __init__(self, val):
		self.val = val
		self.left = None
		self.right = None

class BST:
	size = 0

	def inorder(self, tmp, size=0):
		if tmp:
			self.inorder(tmp.left, self.size)
			print(tmp.val, end=' ')
			self.inorder(tmp.right, self.size)
if __name__ == '__main__':
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		obj = Solution()
		b = BST()
		pt = obj.constructTree(arr, n)
		b.inorder(pt)
		print()


class Solution:

	def constructTree(self, post, n):

		def fun(post, n):
			if n == 0:
				return None
			if n == 1:
				return Node(post[0])
			root = Node(post[-1])
			i = n - 2
			while i >= 0 and post[-1] < post[i]:
				i -= 1
			root.left = fun(post[0:i + 1], i + 1)
			root.right = fun(post[i + 1:-1], n - i - 2)
			return root
		return fun(post, n)


class Solution:

	def constructTree(self, post, n):

		def find(i, j, val):
			if i >= len(post):
				return i
			if i == j:
				if val <= post[i]:
					return i
				else:
					return i + 1
			m = (i + j) // 2
			if val > post[m]:
				return find(m + 1, j, val)
			else:
				return find(i, m, val)

		def recur(i, j):
			if i < 0 or j < 0 or i > j:
				return None
			if i == j:
				return Node(post[i])
			val = post[j]
			curr = Node(val)
			ind = find(i, j - 1, val)
			curr.left = recur(i, ind - 1)
			curr.right = recur(ind, j - 1)
			return curr
		return recur(0, n - 1)


class Solution:

	def constructTree(self, postorder, n):

		def build(l, r):
			if root_index[0] == -1:
				return None
			root_data = postorder[root_index[0]]
			if not l < root_data < r:
				return None
			root_index[0] -= 1
			right = build(root_data, r)
			left = build(l, root_data)
			node = Node(root_data)
			node.left = left
			node.right = right
			return node
		root_index = [n - 1]
		return build(float('-inf'), float('inf'))


class Solution:

	def constructTree(self, post, n):
		n -= 1

		def solve(lower, upper):
			nonlocal n
			if n == -1:
				return None
			if post[n] > upper or post[n] < lower:
				return None
			val = post[n]
			n -= 1
			root = Node(val)
			root.right = solve(val, upper)
			root.left = solve(lower, val)
			return root
		return solve(-float('inf'), float('inf'))


class Solution:

	def constructTree(self, post, n):
		if len(post) == 0:
			return None
		elif len(post) == 1:
			return Node(post[0])
		else:
			rv = post[-1]
			root = Node(rv)
			lst = [i for i in post if i < rv]
			rst = [i for i in post if i > rv]
			root.left = self.constructTree(lst, n)
			root.right = self.constructTree(rst, n)
			return root


class Solution:

	def constructTree(self, post, n):
		import sys
		global idx
		idx = n - 1

		def fun(post, lr, rr):
			global idx
			if idx < 0 or post[idx] < lr or post[idx] > rr:
				return None
			root = Node(post[idx])
			idx -= 1
			root.right = fun(post, root.val, rr)
			root.left = fun(post, lr, root.val)
			return root
		lr = -sys.maxsize
		rr = sys.maxsize
		ans = fun(post, lr, rr)
		return ans


class Solution:

	def constructTree(self, post, n):

		def Cons(ino):
			if not ino:
				return None
			mid = len(ino) // 2
			root = Node(ino[mid])
			root.left = Cons(ino[:mid])
			root.right = Cons(ino[mid + 1:])
			return root
		return Cons(sorted(post))


def tree(post, inorder, st, end, mp):
	if st > end:
		return (None, post)
	value = post.pop(-1)
	root = Node(value)
	ip = mp[value]
	(root.right, post) = tree(post, inorder, ip + 1, end, mp)
	(root.left, post) = tree(post, inorder, st, ip - 1, mp)
	return (root, post)

class Solution:

	def constructTree(self, post, n):
		if n == 1:
			return Node(post[0])
		inorder = sorted(post)
		mp = {}
		for i in range(n):
			mp[inorder[i]] = i
		(root, post) = tree(post, inorder, 0, n - 1, mp)
		return root


class Solution:

	def constructTree(self, post, n):

		def rec(post, l, r):
			if l > r:
				return
			root = Node(post[r])
			mid = r
			while post[mid] >= post[r] and mid >= l:
				mid -= 1
			root.left = rec(post, l, mid)
			root.right = rec(post, mid + 1, r - 1)
			return root
		return rec(post, 0, n - 1)


class Solution:

	def postToBST(self, post, s, e):
		if s > e:
			return None
		mid = (s + e) // 2
		root = Node(post[mid])
		root.left = self.postToBST(post, s, mid - 1)
		root.right = self.postToBST(post, mid + 1, e)
		return root

	def constructTree(self, post, n):
		post.sort()
		return self.postToBST(post, 0, len(post) - 1)


class Solution:

	def constructTree(self, post, n):
		ptr = [n - 1]
		l = -999999999
		r = 9999999999
		return self.func(post, ptr, l, r)

	def func(self, post, ptr, l, r):
		if ptr[0] < 0:
			return
		if l > r:
			return
		if l > post[ptr[0]] or r < post[ptr[0]]:
			return
		temp = ptr.copy()
		root = Node(post[ptr[0]])
		ptr[0] -= 1
		root.right = self.func(post, ptr, root.val + 1, r)
		root.left = self.func(post, ptr, l, root.val - 1)
		return root


class Solution:

	def constructTree(self, post, n):
		d = post[-1]
		n = Node(d)
		post.pop()
		for i in post:
			self.insert(i, n)
		return n

	def insert(self, key, root):
		if root.val > key:
			if root.left == None:
				root.left = Node(key)
			else:
				self.insert(key, root.left)
		elif root.right == None:
			root.right = Node(key)
		else:
			self.insert(key, root.right)


class Solution:

	def constructTree(self, post, n):
		if not post or len(post) == 0:
			return None
		self.ptr = len(post) - 1
		self.post = post

		def formTree(lowerBound):
			if self.ptr < 0:
				return
			if self.post[self.ptr] > lowerBound:
				node = Node(self.post[self.ptr])
				self.ptr -= 1
				node.right = formTree(node.val)
				node.left = formTree(lowerBound)
				return node
		return formTree(float('-inf'))


def arrToBST(arr):
	if not arr:
		return None
	mid = len(arr) // 2
	root = Node(arr[mid])
	root.left = arrToBST(arr[:mid])
	root.right = arrToBST(arr[mid + 1:])
	return root

class Solution:

	def constructTree(self, post, n):
		post = sorted(post)
		return arrToBST(post)


class Solution:

	def constructTree(self, post, n):
		index = len(post) - 1

		def helper(preorder, lowerbound):
			nonlocal index
			if index < 0 or preorder == [] or preorder[index] < lowerbound:
				return None
			root = Node(preorder[index])
			index -= 1
			root.right = helper(preorder, root.val)
			root.left = helper(preorder, lowerbound)
			return root
		return helper(post, float('-inf'))


class Node:

	def __init__(self, data):
		self.left = None
		self.right = None
		self.val = data

class Solution:

	def constructTree(self, a, n):
		root = Node(a[n - 1])
		s = []
		s.append(root)
		i = n - 2
		while len(s) > 0 and i >= 0:
			x = Node(a[i])
			temp = None
			while len(s) > 0 and a[i] < s[-1].val:
				temp = s.pop()
			if temp != None:
				temp.left = x
			else:
				s[-1].right = x
			s.append(x)
			i -= 1
		return root


class Solution:

	def makeBST(self, post, i, j):
		global PSE
		if i > j:
			return None
		root = Node(val=post[j])
		root.left = self.makeBST(post, i, PSE[j])
		root.right = self.makeBST(post, PSE[j] + 1, j - 1)
		return root

	def constructTree(self, post, n):
		global PSE
		PSE = [0] * n
		stk = []
		stk.append(n - 1)
		for i in range(n - 2, -1, -1):
			while stk and post[i] < post[stk[-1]]:
				PSE[stk[-1]] = i
				stk.pop()
			stk.append(i)
		while stk:
			PSE[stk[-1]] = -1
			stk.pop()
		return self.makeBST(post, 0, n - 1)


class Solution:

	def helper(self, post, l, r):
		if l > r:
			return None
		m = (l + r) // 2
		root = Node(post[m])
		root.left = self.helper(post, l, m - 1)
		root.right = self.helper(post, m + 1, r)
		return root

	def constructTree(self, post, n):
		post.sort()
		l = 0
		r = len(post) - 1
		return self.helper(post, l, r)


class Solution:

	def solve(self, listt, l, r):
		if l > r:
			return None
		mid = int((l + r) / 2)
		root = Node(listt[mid])
		root.left = self.solve(listt, l, mid - 1)
		root.right = self.solve(listt, mid + 1, r)
		return root

	def constructTree(self, post, n):
		post.sort()
		l = 0
		r = len(post) - 1
		x = self.solve(post, l, r)
		return x


class Node:

	def __init__(self, val):
		self.data = val
		self.left = None
		self.right = None

def make_bst(i, post, lb):
	if i[0] < 0:
		return
	if post[i[0]] < lb:
		return None
	else:
		val = post[i[0]]
		node = Node(val)
		i[0] -= 1
		node.right = make_bst(i, post, val)
		node.left = make_bst(i, post, lb)
		return node
import math

class Solution:

	def constructTree(self, post, n):
		i = [len(post) - 1]
		root = make_bst(i, post, -math.inf)
		return root


class Solution:

	def construct(self, inorder, post):
		if inorder:
			x = inorder.index(post.pop())
			root = Node(inorder[x])
			root.right = self.construct(inorder[x + 1:], post)
			root.left = self.construct(inorder[:x], post)
			return root
		return None

	def constructTree(self, post, n):
		inorder = sorted(post)
		return self.construct(inorder, post)


class Solution:

	def __init__(self):
		self.key = 0

	def buildTree(self, A, limit):
		if self.key < 0 or A == [] or A[self.key] < limit:
			return None
		root = Node(A[self.key])
		self.key -= 1
		root.right = self.buildTree(A, root.val)
		root.left = self.buildTree(A, limit)
		return root

	def constructTree(self, post, n):
		self.key = len(post) - 1
		return self.buildTree(post, float('-inf'))


class Solution:

	def constructTree(self, post, n):
		lr = float('-inf')
		rr = float('inf')
		self.idx = len(post) - 1

		def postorder1(post, lr, rr):
			if self.idx < 0 or post[self.idx] < lr or post[self.idx] > rr:
				return None
			node = Node(post[self.idx])
			self.idx -= 1
			node.right = postorder1(post, node.val, rr)
			node.left = postorder1(post, lr, node.val)
			return node
		return postorder1(post, lr, rr)


class Solution:

	def constructTree(self, post, n):
		post.sort()
		return self.solve(post, 0, len(post) - 1)

	def solve(self, arr, start, end):
		if start > end:
			return
		mid = (start + end) // 2
		node = Node(arr[mid])
		node.left = self.solve(arr, start, mid - 1)
		node.right = self.solve(arr, mid + 1, end)
		return node


class Solution:

	def constructTree(self, post, n):
		self.ind = n - 1
		ll = -float('inf')
		rr = float('inf')
		return self.tree(post, ll, rr)

	def tree(self, post, ll, rr):
		if self.ind < 0 or post[self.ind] < ll or post[self.ind] > rr:
			return None
		root = Node(post[self.ind])
		self.ind -= 1
		root.right = self.tree(post, root.val, rr)
		root.left = self.tree(post, ll, root.val)
		return root


class Solution:

	def getNode(self, val):
		new_node = Node(val)
		return new_node

	def constructBST(self, post, pos, root, mi, mx):
		if pos < 0 or post[pos] < mi or post[pos] > mx:
			return pos
		if post[pos] > root.val:
			root.right = self.getNode(post[pos])
			pos -= 1
			pos = self.constructBST(post, pos, root.right, root.val + 1, mx)
		if pos < 0 or post[pos] < mi or post[pos] > mx:
			return pos
		if post[pos] < root.val:
			root.left = self.getNode(post[pos])
			pos -= 1
			pos = self.constructBST(post, pos, root.left, mi, root.val - 1)
		return pos

	def constructTree(self, post, n):
		n = len(post)
		if n == 0:
			return None
		if n == 1:
			return self.getNode(post[-1])
		else:
			root = self.getNode(post[-1])
			self.constructBST(post, n - 2, root, -1234567890, 1234567890)
			return root


class Solution:

	def constructTree(self, post, n):
		if len(post) == 0:
			return
		else:
			post.sort()
			for i in range(n):
				print(post[i], end=' ')


import sys

class Solution:

	def cbst(self, post, lb, ub):
		global i
		if i < 0 or post[i] > ub or post[i] < lb:
			return None
		root = Node(post[i])
		i -= 1
		root.right = self.cbst(post, root.val, ub)
		root.left = self.cbst(post, lb, root.val)
		return root

	def constructTree(self, post, n):
		ub = sys.maxsize
		lb = -sys.maxsize
		global i
		i = n - 1
		root = self.cbst(post, lb, ub)
		return root


class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

class Solution:

	def constructTree(self, post, n):
		idx = n - 1
		lr = float('-inf')
		rr = float('inf')

		def solve(left, right):
			nonlocal idx
			if idx < 0 or post[idx] < left or post[idx] > right:
				return
			root = Node(post[idx])
			idx -= 1
			root.right = solve(root.val, right)
			root.left = solve(left, root.val)
			return root
		return solve(lr, rr)