Given an array A[ ] and its size N your task is to complete two functions  a constructST  function which builds the segment tree  and a function RMQ which finds range minimum query in a range [a,b] of the given array.
Input:
The task is to complete two functions constructST and RMQ.
The constructST function builds the segment tree and takes two arguments the array A[ ] and the size of the array N.
It returns a pointer to the first element of the segment tree array.
The RMQ function takes 4 arguments the first being the segment tree st constructed, second being the size N and then third and forth arguments are the range of query a and b. The function RMQ returns the min of the elements in the array from index range a and b. There are multiple test cases. For each test case, this method will be called individually.
Output:
The function RMQ should return the min element in the array from range a to b.
Example:
Input (To be used only for expected output) 
1
4
1 2 3 4
2
0 2 2 3
Output
1 3
Explanation
1. For query 1 ie 0 2 the element in this range are 1 2 3 
   and the min element is 1. 
2. For query 2 ie 2 3 the element in this range are 3 4 
   and the min element is 3.
Constraints:
1<=T<=100
1<=N<=10^3+1
1<=A[i]<=10^9
1<=Q(no of queries)<=10000
0<=a<=b

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Range queries

Segment trees revisited

Starter code: #User function Template for python3



def constructST(arr,n):



    return



def RMQ(st ,  n,  qs,  qe):

    

    return



Solutions:
import sys

def constructST(arr, n):
	st = [sys.maxsize] * (4 * n)

	def build(node, l, r):
		if l == r:
			st[node] = arr[l]
		else:
			m = (l + r) // 2
			build(2 * node + 1, l, m)
			build(2 * node + 2, m + 1, r)
			st[node] = min(st[2 * node + 1], st[2 * node + 2])
	build(0, 0, n - 1)
	return st

def RMQ(st, n, qs, qe):

	def mini(node, l, r, qs, qe):
		if qs > r or qe < l:
			return sys.maxsize
		if qs <= l and qe >= r:
			return st[node]
		m = (l + r) // 2
		return min(mini(2 * node + 1, l, m, qs, qe), mini(2 * node + 2, m + 1, r, qs, qe))
	return mini(0, 0, n - 1, qs, qe)


def constructST(arr, n):
	seg = [0] * 4 * n

	def build(ind, low, high):
		if low == high:
			seg[ind] = arr[low]
			return
		mid = low + high >> 1
		build(ind * 2 + 1, low, mid)
		build(ind * 2 + 2, mid + 1, high)
		seg[ind] = min(seg[ind * 2 + 1], seg[ind * 2 + 2])
	build(0, 0, n - 1)
	return seg

def RMQ(st, n, qs, qe):
	seg = st

	def query(ind, low, high, l, r):
		if low > r or l > high:
			return float('inf')
		if low >= l and high <= r:
			return seg[ind]
		mid = low + high >> 1
		left = query(ind * 2 + 1, low, mid, l, r)
		right = query(ind * 2 + 2, mid + 1, high, l, r)
		return min(left, right)
	return query(0, 0, n - 1, qs, qe)


def constructST(arr, n):
	seg_tree = [arr]
	while len(seg_tree[-1]) > 1:
		seg_tree.append([])
		for i in range(0, len(seg_tree[-2]), 2):
			seg_tree[-1].append(min(seg_tree[-2][i:i + 2]))
	return seg_tree

def RMQ(st, n, qs, qe):
	compare_numbers = []
	level = 0
	while qs < qe:
		if qs % 2 == 1:
			compare_numbers.append(st[level][qs])
			qs += 1
		if qe % 2 == 0:
			compare_numbers.append(st[level][qe])
			qe -= 1
		qs //= 2
		qe //= 2
		level += 1
	if qs == qe:
		compare_numbers.append(st[level][qs])
	return min(compare_numbers)


import math

def constructST(arr, n):
	newarr = [float('inf')] * (2 ** math.ceil(math.log(len(arr), 2)) * 2 - 1)

	def con(i, j, pos):
		if i == j:
			newarr[pos] = arr[i]
			return
		mid = (i + j) // 2
		con(i, mid, 2 * pos + 1)
		con(mid + 1, j, 2 * pos + 2)
		newarr[pos] = min(newarr[2 * pos + 1], newarr[2 * pos + 2])
	con(0, len(arr) - 1, 0)
	return newarr

def RMQ(st, n, qs, qe):

	def query(i, j, qs, qe, pos):
		if i >= qs and qe >= j:
			return st[pos]
		elif qs > j or i > qe:
			return float('inf')
		else:
			mid = (i + j) // 2
			return min(query(i, mid, qs, qe, 2 * pos + 1), query(mid + 1, j, qs, qe, 2 * pos + 2))
	return query(0, n - 1, qs, qe, 0)


from sys import maxsize

class SegmentTree:

	def __init__(self, nums):
		self.nums = nums
		self.length = len(nums)
		self.segmentTree = [0] * (self.length * 4)
		self.construct(start=0, end=self.length - 1, currentIndex=0)

	def construct(self, start, end, currentIndex):
		if start == end:
			self.segmentTree[currentIndex] = self.nums[start]
			return
		mid = start + (end - start) // 2
		self.construct(start, mid, 2 * currentIndex + 1)
		self.construct(mid + 1, end, 2 * currentIndex + 2)
		self.segmentTree[currentIndex] = min(self.segmentTree[2 * currentIndex + 1], self.segmentTree[2 * currentIndex + 2])
		return

	def update(self, value, index, start=0, end=None, currentIndex=0):
		if end == None:
			end = self.length - 1
		if currentIndex == 0:
			self.nums[index] = value
		if start == end:
			self.segmentTree[currentIndex] = self.nums[index]
		mid = start + (end - start) // 2
		if index <= mid:
			self.update(value, index, start, mid, 2 * currentIndex + 1)
		else:
			self.update(value, index, mid + 1, end, 2 * currentIndex + 2)
		self.segmentTree[currentIndex] = min(self.segmentTree[2 * currentIndex + 1], self.segmentTree[2 * currentIndex + 2])
		return

	def rangeMin(self, left, right, start=0, end=None, currentIndex=0):
		if end == None:
			end = self.length - 1
		if left > end or start > right:
			return maxsize
		if left <= start and right >= end:
			return self.segmentTree[currentIndex]
		mid = start + (end - start) // 2
		leftMin = self.rangeMin(left, right, start, mid, 2 * currentIndex + 1)
		rightMin = self.rangeMin(left, right, mid + 1, end, 2 * currentIndex + 2)
		return min(leftMin, rightMin)

def constructST(arr, n):
	S = SegmentTree(arr)
	return S

def RMQ(st, n, qs, qe):
	return st.rangeMin(qs, qe)


import sys
from math import ceil, log2

def buildST(nIdx, st, arr, l, r):
	if l == r:
		st[nIdx] = arr[l]
		return st[nIdx]
	mid = (l + r) // 2
	st[nIdx] = min(buildST(2 * nIdx + 1, st, arr, l, mid), buildST(2 * nIdx + 2, st, arr, mid + 1, r))
	return st[nIdx]

def query(nIdx, st, qs, qe, l, r):
	if qs <= l and qe >= r:
		return st[nIdx]
	if l > qe or r < qs:
		return sys.maxsize
	mid = (l + r) // 2
	return min(query(2 * nIdx + 1, st, qs, qe, l, mid), query(2 * nIdx + 2, st, qs, qe, mid + 1, r))

def constructST(arr, n):
	h = ceil(log2(n))
	st = [sys.maxsize] * (2 * 2 ** h - 1)
	buildST(0, st, arr, 0, n - 1)
	return st

def RMQ(st, n, qs, qe):
	return query(0, st, qs, qe, 0, n - 1)


import sys

def buildST(nIdx, st, arr, l, r):
	if l == r:
		st[nIdx] = arr[l]
		return st[nIdx]
	mid = (l + r) // 2
	st[nIdx] = min(buildST(2 * nIdx + 1, st, arr, l, mid), buildST(2 * nIdx + 2, st, arr, mid + 1, r))
	return st[nIdx]

def query(nIdx, st, qs, qe, l, r):
	if qs <= l and qe >= r:
		return st[nIdx]
	if l > qe or r < qs:
		return sys.maxsize
	mid = (l + r) // 2
	return min(query(2 * nIdx + 1, st, qs, qe, l, mid), query(2 * nIdx + 2, st, qs, qe, mid + 1, r))

def constructST(arr, n):
	st = [sys.maxsize] * (2 * n + 100)
	buildST(0, st, arr, 0, n - 1)
	return st

def RMQ(st, n, qs, qe):
	return query(0, st, qs, qe, 0, n - 1)


tree = [0] * (1001 * 4)

def build(node, st, ed, a):
	if st == ed:
		tree[node] = a[st]
	else:
		build(2 * node, st, (st + ed) // 2, a)
		build(2 * node + 1, (st + ed) // 2 + 1, ed, a)
		tree[node] = min(tree[2 * node], tree[2 * node + 1])

def constructST(arr, n):
	build(1, 0, n - 1, arr)
	return

def query(node, st, ed, l, r):
	if r < st or l > ed:
		return 10000000000000
	if st == ed:
		return tree[node]
	if st >= l and ed <= r:
		return tree[node]
	else:
		return min(query(2 * node, st, (st + ed) // 2, l, r), query(2 * node + 1, (st + ed) // 2 + 1, ed, l, r))

def RMQ(st, n, qs, qe):
	return query(1, 0, n - 1, qs, qe)
	return


class SegmentTree:

	def __init__(self, data, merge, neutro):
		self.data = [i for i in data]
		(self.N, self.merge, self.neutro) = (len(data), merge, neutro)
		self.tree = [0 for i in range(4 * self.N)]
		self.__Build(1, 0, self.N - 1)

	def __Build(self, n, b, e):
		if b == e:
			self.tree[n] = self.data[b]
		else:
			m = (b + e) // 2
			self.__Build(2 * n, b, m)
			self.__Build(2 * n + 1, m + 1, e)
			self.tree[n] = self.merge(self.tree[2 * n], self.tree[2 * n + 1])

	def __Query(self, n, b, e, i, j):
		if b > j or e < i:
			return self.neutro
		if b >= i and e <= j:
			return self.tree[n]
		m = b + e >> 1
		return self.merge(self.__Query(n * 2, b, m, i, j), self.__Query(n * 2 + 1, m + 1, e, i, j))

	def Query(self, i, j):
		return self.__Query(1, 0, self.N - 1, i, j)

	def __Update(self, n, b, e, i, v):
		if b == e:
			(self.tree[n], self.data[b]) = (v, v)
		else:
			m = (b + e) // 2
			if i <= m:
				self.__Update(2 * n, b, m, i, v)
			else:
				self.__Update(2 * n + 1, m + 1, e, i, v)
			self.tree[n] = self.merge(self.tree[2 * n], self.tree[2 * n + 1])

	def Update(self, i, v):
		self.__Update(1, 0, self.N - 1, i, v)

def constructST(arr, n):
	st = SegmentTree(arr, lambda x, y: min(x, y), 1e+100)
	return st

def RMQ(st, n, qs, qe):
	return st.Query(qs, qe)


def constructST(arr, n):
	tree = [0] * (4 * n)

	def build(i, L, R):
		nonlocal tree
		if L == R:
			tree[i] = arr[L]
			return
		M = L + (R - L) // 2
		build(2 * i + 1, L, M)
		build(2 * i + 2, M + 1, R)
		tree[i] = min(tree[2 * i + 1], tree[2 * i + 2])
	build(0, 0, n - 1)
	return tree

def RMQ(st, n, qs, qe):

	def query(i, L, R):
		if R < qs or qe < L:
			return float('inf')
		if L == R:
			return st[i]
		if qs <= L <= R <= qe:
			return st[i]
		M = L + (R - L) // 2
		return min(query(2 * i + 1, L, M), query(2 * i + 2, M + 1, R))
	return query(0, 0, n - 1)


def constructSTUtil(root, arr, l, r, si):
	if l == r:
		root[si] = arr[l]
		return
	m = (l + r) // 2
	constructSTUtil(root, arr, l, m, 2 * si + 1)
	constructSTUtil(root, arr, m + 1, r, 2 * si + 2)
	root[si] = min(root[2 * si + 1], root[2 * si + 2])

def RangeMin(root, qs, qe, l, r, si):
	if l > qe or r < qs:
		return float('inf')
	if l >= qs and r <= qe:
		return root[si]
	m = (l + r) // 2
	return min(RangeMin(root, qs, qe, l, m, 2 * si + 1), RangeMin(root, qs, qe, m + 1, r, 2 * si + 2))

def constructST(arr, n):
	root = [float('inf')] * 4 * n
	constructSTUtil(root, arr, 0, n - 1, 0)
	return root

def RMQ(st, n, qs, qe):
	return RangeMin(st, qs, qe, 0, n - 1, 0)


def constructST(arr, n):
	totalLength = n
	segmentTree = [float('inf')] * (totalLength * 4)
	constructSegmentTree(0, totalLength - 1, 0, arr, segmentTree)
	return segmentTree

def constructSegmentTree(start, end, currIndex, nums, segmentTree):
	if start == end:
		segmentTree[currIndex] = nums[start]
		return
	mid = start + (end - start) // 2
	leftIndex = 2 * currIndex + 1
	rightIndex = 2 * currIndex + 2
	constructSegmentTree(start, mid, leftIndex, nums, segmentTree)
	constructSegmentTree(mid + 1, end, rightIndex, nums, segmentTree)
	segmentTree[currIndex] = min(segmentTree[leftIndex], segmentTree[rightIndex])
	return

def RMQ(st, n, qs, qe):
	return getRangeMinimum(0, n - 1, 0, st, qs, qe)

def getRangeMinimum(start, end, currIndex, segmentTree, left, right):
	if start > right or end < left:
		return float('inf')
	if start >= left and end <= right:
		return segmentTree[currIndex]
	mid = start + (end - start) // 2
	leftIndex = 2 * currIndex + 1
	rightIndex = 2 * currIndex + 2
	leftVal = getRangeMinimum(start, mid, leftIndex, segmentTree, left, right)
	rightVal = getRangeMinimum(mid + 1, end, rightIndex, segmentTree, left, right)
	return min(leftVal, rightVal)


class Node:

	def __init__(self):
		self.min = float('inf')
		self.left = self.right = None
		self.lChild = self.rChild = None

def createSgTree(nums, l: int, r: int):
	root = Node()
	root.right = r
	root.left = l
	if l == r:
		root.min = nums[l]
	else:
		mid = (l + r) // 2
		root.lChild = createSgTree(nums, l, mid)
		root.rChild = createSgTree(nums, mid + 1, r)
		root.min = min(root.lChild.min, root.rChild.min)
	return root

def rangeMin(root: Node, ql, qr):
	if ql <= root.left and root.right <= qr:
		return root.min
	if root.left > qr or root.right < ql:
		return float('inf')
	return min(rangeMin(root.lChild, ql, qr), rangeMin(root.rChild, ql, qr))

def constructST(arr, n):
	root = createSgTree(arr, 0, n - 1)
	return root

def RMQ(st, n, qs, qe):
	return rangeMin(st, qs, qe)


import math

def constructST(arr, n):
	tree = [0] * (2 * n)
	for i in range(n):
		tree[i + n] = arr[i]
	for i in range(n - 1, 0, -1):
		tree[i] = min(tree[i << 1], tree[i << 1 | 1])
	return tree

def RMQ(st, n, qs, qe):
	qs += n
	qe += n + 1
	ans = math.inf
	l = qs
	r = qe
	while l < r:
		if l & 1:
			ans = min(ans, st[l])
			l += 1
		if r & 1:
			r -= 1
			ans = min(ans, st[r])
		l >>= 1
		r >>= 1
	return ans


import math
tree = None

def buildTree(pos, left, right, arr):
	global tree
	if left == right:
		tree[pos] = arr[left]
		return
	mid = (left + right) // 2
	buildTree((pos << 1) + 1, left, mid, arr)
	buildTree((pos << 1) + 2, mid + 1, right, arr)
	tree[pos] = min(tree[(pos << 1) + 1], tree[(pos << 1) + 2])

def constructST(arr, n):
	global tree
	tree = [0] * (4 * n)
	buildTree(0, 0, n - 1, arr)
	return tree

def query(pos, left, right, l, r, tree):
	if r < left or right < l:
		return math.inf
	if l <= left and right <= r:
		return tree[pos]
	mid = (left + right) // 2
	return min(query((pos << 1) + 1, left, mid, l, r, tree), query((pos << 1) + 2, mid + 1, right, l, r, tree))

def RMQ(st, n, qs, qe):
	return query(0, 0, n - 1, qs, qe, st)


def constructST(arr, n):
	seg = [None for i in range(4 * n)]

	def solve(ss, se, si):
		if ss == se:
			seg[si] = arr[ss]
			return seg[si]
		mid = (ss + se) // 2
		seg[si] = min(solve(ss, mid, 2 * si + 1), solve(mid + 1, se, 2 * si + 2))
		return seg[si]
	solve(0, n - 1, 0)
	return seg

def RMQ(st, n, qs, qe):

	def calc(qs, qe, ss, se, si):
		if qe < ss or qs > se:
			return 2 ** 31
		if qs <= ss and qe >= se:
			return st[si]
		if se > ss:
			mid = (ss + se) // 2
			return min(calc(qs, qe, ss, mid, 2 * si + 1), calc(qs, qe, mid + 1, se, 2 * si + 2))
		return 2 ** 31
	return calc(qs, qe, 0, n - 1, 0)


from math import ceil, log2

def construct(arr, segTree, low, high, pos):
	if low == high:
		segTree[pos] = arr[low]
		return
	mid = (low + high) // 2
	construct(arr, segTree, low, mid, 2 * pos + 1)
	construct(arr, segTree, mid + 1, high, 2 * pos + 2)
	segTree[pos] = min(segTree[2 * pos + 1], segTree[2 * pos + 2])

def constructST(arr, n):
	segTree = [0] * (4 * n + 1)
	construct(arr, segTree, 0, n - 1, 0)
	return segTree

def rangeMinQuery(segTree, low, high, qlow, qhigh, pos):
	if qlow <= low and qhigh >= high:
		return segTree[pos]
	if qlow > high or qhigh < low:
		return 100000007
	mid = (low + high) // 2
	return min(rangeMinQuery(segTree, low, mid, qlow, qhigh, 2 * pos + 1), rangeMinQuery(segTree, mid + 1, high, qlow, qhigh, 2 * pos + 2))

def RMQ(st, n, qs, qe):
	return rangeMinQuery(segTree, 0, n - 1, qs, qe, 0)


def constructTree(ind, low, high, arr, segment):
	if low == high:
		segment[ind] = arr[low]
		return
	mid = (low + high) // 2
	constructTree(2 * ind + 1, low, mid, arr, segment)
	constructTree(2 * ind + 2, mid + 1, high, arr, segment)
	segment[ind] = min(segment[2 * ind + 1], segment[2 * ind + 2])

def constructST(arr, n):
	segment = [0] * (4 * 10 ** 5 + 1)
	constructTree(0, 0, n - 1, arr, segment)
	return segment

def performQueries(ind, low, high, l, r, st):
	if low >= l and high <= r:
		return st[ind]
	if high < l or low > r:
		return float('inf')
	mid = (low + high) // 2
	val1 = performQueries(2 * ind + 1, low, mid, l, r, st)
	val2 = performQueries(2 * ind + 2, mid + 1, high, l, r, st)
	return min(val1, val2)

def RMQ(st, n, l, r):
	return performQueries(0, 0, n - 1, l, r, st)


import sys
from math import ceil, log2
INT_MAX = sys.maxsize

def minVal(x, y):
	return x if x < y else y

def getMid(s, e):
	return s + (e - s) // 2

def RMQUtil(st, ss, se, qs, qe, index):
	if qs <= ss and qe >= se:
		return st[index]
	if se < qs or ss > qe:
		return INT_MAX
	mid = getMid(ss, se)
	return minVal(RMQUtil(st, ss, mid, qs, qe, 2 * index + 1), RMQUtil(st, mid + 1, se, qs, qe, 2 * index + 2))

def RMQ(st, n, qs, qe):
	if qs < 0 or qe > n - 1 or qs > qe:
		print('Invalid Input')
		return -1
	return RMQUtil(st, 0, n - 1, qs, qe, 0)

def constructSTUtil(arr, ss, se, st, si):
	if ss == se:
		st[si] = arr[ss]
		return arr[ss]
	mid = getMid(ss, se)
	st[si] = minVal(constructSTUtil(arr, ss, mid, st, si * 2 + 1), constructSTUtil(arr, mid + 1, se, st, si * 2 + 2))
	return st[si]

def constructST(arr, n):
	x = int(ceil(log2(n)))
	max_size = 2 * int(2 ** x) - 1
	st = [0] * max_size
	constructSTUtil(arr, 0, n - 1, st, 0)
	return st


import sys

class SegmentTree:

	class Node:

		def __init__(self, i, j, minVal):
			self.start = i
			self.end = j
			self.val = minVal
			self.left = None
			self.right = None

		def __repr__(self):
			return 'minVal: {} for range {}- {}'.format(self.val, self.start, self.end)

	def __init__(self, arr):
		self.root = self.createTree(0, len(arr) - 1, arr)

	def createTree(self, start, end, arr):
		if start > end:
			raise Exception('start cannot be greater than end')
		if start == end:
			return self.Node(start, end, arr[start])
		else:
			mid = (start + end) // 2
			left = self.createTree(start, mid, arr)
			right = self.createTree(mid + 1, end, arr)
			node = self.Node(start, end, min(left.val, right.val))
			node.left = left
			node.right = right
			return node

	def printTree(self):
		if self.root:
			print(self.root)
			self.printTree(self.root.left)
			self.printTree(self.root.right)

	def findMinimum(self, node, qs, qe):
		if self.fullOverlap(node, qs, qe):
			return node.val
		elif self.partialOverlap(node, qs, qe):
			return min(self.findMinimum(node.left, qs, qe), self.findMinimum(node.right, qs, qe))
		else:
			return sys.maxsize

	def fullOverlap(self, node, qs, qe):
		return node.start >= qs and node.start <= qe and (node.end >= qs) and (node.end <= qe)

	def partialOverlap(self, node, qs, qe):
		return not self.fullOverlap(node, qs, qe) and self.overlap(node.start, node.end, qs, qe)

	def overlap(self, i1, i2, i3, i4):
		return i2 >= i3 and i4 >= i1

def constructST(arr, n):
	return SegmentTree(arr)

def RMQ(st, n, qs, qe):
	return st.findMinimum(st.root, qs, qe)


from math import log2, ceil

def constructSTUtil(st, arr, arrs, arre, curri):
	if arrs == arre:
		st[curri] = arr[arrs]
		return arr[arrs]
	mid = (arrs + arre) // 2
	st[curri] = min(constructSTUtil(st, arr, arrs, mid, 2 * curri + 1), constructSTUtil(st, arr, mid + 1, arre, 2 * curri + 2))
	return st[curri]

def constructST(arr, n):
	h = int(ceil(log2(n)))
	st = [0] * (2 ** (h + 1) - 1)
	constructSTUtil(st, arr, 0, n - 1, 0)
	return st

def RMQUtil(st, n, qs, qe, ss, se, ci):
	if qe < ss or qs > se:
		return float('inf')
	if ss >= qs and se <= qe:
		return st[ci]
	mid = (ss + se) // 2
	return min(RMQUtil(st, n, qs, qe, ss, mid, 2 * ci + 1), RMQUtil(st, n, qs, qe, mid + 1, se, 2 * ci + 2))

def RMQ(st, n, qs, qe):
	qs = min(qs, qe)
	qe = max(qs, qe)
	(ss, se) = (0, n - 1)
	return RMQUtil(st, n, qs, qe, ss, se, 0)


import sys
seg = [0] * 100000

def build(ind, arr, low, high):
	if low == high:
		seg[ind] = arr[low]
		return
	mid = low + (high - low) // 2
	build(2 * ind + 1, arr, low, mid)
	build(2 * ind + 2, arr, mid + 1, high)
	seg[ind] = min(seg[2 * ind + 1], seg[2 * ind + 2])

def constructST(arr, n):
	build(0, arr, 0, n - 1)
	return seg

def query(ind, low, high, l, r):
	if l > high or r < low:
		return sys.maxsize
	if l <= low and high <= r:
		return seg[ind]
	mid = low + (high - low) // 2
	left = query(2 * ind + 1, low, mid, l, r)
	right = query(2 * ind + 2, mid + 1, high, l, r)
	return min(left, right)

def RMQ(st, n, qs, qe):
	return query(0, 0, n - 1, qs, qe)


from math import inf

class Node:

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

def helper(arr, low, high):
	if low > high:
		return None
	elif low == high:
		return Node(arr[low])
	mid = (low + high) // 2
	curr_node = Node(inf)
	(left, right) = (helper(arr, low, mid), helper(arr, mid + 1, high))
	if left:
		curr_node.val = min(curr_node.val, left.val)
		curr_node.left = left
	if right:
		curr_node.val = min(curr_node.val, right.val)
		curr_node.right = right
	return curr_node

def constructST(arr, n):
	return helper(arr, 0, n - 1)

def query_helper(tree, start, end, qs, qe):
	if start > end:
		return inf
	if start == end:
		return tree.val
	mid = (start + end) // 2
	if qs == start and qe == end:
		return tree.val
	left = right = inf
	if qs > mid:
		right = query_helper(tree.right, mid + 1, end, qs, qe)
	elif qe <= mid:
		left = query_helper(tree.left, start, mid, qs, qe)
	else:
		(left, right) = (query_helper(tree.left, start, mid, qs, mid), query_helper(tree.right, mid + 1, end, mid + 1, qe))
	return min(left, right)

def RMQ(st, n, qs, qe):
	return query_helper(st, 0, n - 1, qs, qe)


import sys
from math import ceil, log2
INT_MAX = float('inf')

def RMQUtil(st, ss, se, qs, qe, index):
	if qs <= ss and qe >= se:
		return st[index]
	if se < qs or ss > qe:
		return INT_MAX
	mid = (ss + se) // 2
	a = RMQUtil(st, ss, mid, qs, qe, 2 * index + 1)
	b = RMQUtil(st, mid + 1, se, qs, qe, 2 * index + 2)
	return min(a, b)

def RMQ(st, n, qs, qe):
	if qs < 0 or qe > n - 1 or qs > qe:
		return -1
	return RMQUtil(st, 0, n - 1, qs, qe, 0)

def constructSTUtil(arr, ss, se, st, si):
	if ss == se:
		st[si] = arr[ss]
		return arr[ss]
	mid = (ss + se) // 2
	a = constructSTUtil(arr, ss, mid, st, si * 2 + 1)
	b = constructSTUtil(arr, mid + 1, se, st, si * 2 + 2)
	st[si] = min(a, b)
	return st[si]

def constructST(arr, n):
	x = int(ceil(log2(n)))
	max_size = int(pow(2, x + 1)) - 1
	st = [0] * max_size
	constructSTUtil(arr, 0, n - 1, st, 0)
	return st


from math import ceil, log2
import sys
sys.setrecursionlimit(1 << 12)

def stHelp(st, arr, ss, se, si):
	if ss == se:
		st[si] = arr[ss]
		return arr[se]
	mid = (ss + se) // 2
	a = stHelp(st, arr, ss, mid, 2 * si + 1)
	b = stHelp(st, arr, mid + 1, se, 2 * si + 2)
	st[si] = min(a, b)
	return st[si]

def constructST(arr, n):
	h = int(ceil(log2(n)))
	maxNodes = pow(2, h + 1) - 1
	st = [float('inf')] * maxNodes
	stHelp(st, arr, 0, n - 1, 0)
	return st

def RMQHelp(st, ss, se, qs, qe, si):
	if si > len(st) - 1:
		return float('inf')
	if ss >= qs and se <= qe:
		return st[si]
	if qs > se and qe < ss:
		return float('inf')
	mid = (ss + se) // 2
	a = RMQHelp(st, ss, mid, qs, qe, 2 * si + 1)
	b = RMQHelp(st, mid + 1, se, qs, qe, 2 * si + 2)
	return min(a, b)

def RMQ(st, n, qs, qe):
	if qs < 0 or qe >= n or qs > qe:
		return -1
	ans = RMQHelp(st, 0, n - 1, qs, qe, 0)
	return ans


from math import ceil, log2

def midE(left, right):
	mid1 = left + (right - left) // 2
	return mid1

def cSegTree(arr, tree, left, right, index):
	if right == left:
		tree[index] = arr[left]
		return tree[index]
	if right < left:
		return 10 ** 9
	mid = midE(left, right)
	m1 = cSegTree(arr, tree, left, mid, 2 * index + 1)
	m2 = cSegTree(arr, tree, mid + 1, right, 2 * index + 2)
	tree[index] = min(m1, m2)
	return tree[index]

def constructST(arr, n):
	x = int(ceil(log2(n)))
	max_size = 2 * int(2 ** x) - 1
	segTree = [0] * max_size
	t = cSegTree(arr, segTree, 0, n - 1, 0)
	return segTree

def RMQ1(st, left, right, qs, qe, index):
	if left >= qs and right <= qe:
		return st[index]
	if left > qe or right < qs:
		return 10 ** 9
	mid = midE(left, right)
	m1 = RMQ1(st, left, mid, qs, qe, 2 * index + 1)
	m2 = RMQ1(st, mid + 1, right, qs, qe, 2 * index + 2)
	return min(m1, m2)

def RMQ(st, n, qs, qe):
	ans = RMQ1(st, 0, n - 1, qs, qe, 0)
	return ans


def constructST(arr, n):
	tree = [0 for _ in range(4 * n)]
	cst(tree, arr, 0, n - 1, 0)
	return tree

def cst(t, a, ss, se, si):
	if ss == se:
		t[si] = a[ss]
		return t[si]
	mid = ss + (se - ss) // 2
	t[si] = min(cst(t, a, ss, mid, 2 * si + 1), cst(t, a, mid + 1, se, 2 * si + 2))
	return t[si]

def RMQ(st, n, qs, qe):
	if qs < 0 or qe > n - 1 or qs > qe:
		print('Invalid Input')
		return -1

	def rm(ss, se, si):
		if ss > qe or se < qs:
			return 99999999999
		if qs <= ss and qe >= se:
			return st[si]
		mid = ss + (se - ss) // 2
		return min(rm(ss, mid, 2 * si + 1), rm(mid + 1, se, 2 * si + 2))
	return rm(0, n - 1, 0)


from math import log2, ceil

def constructSTUtil(st, arr, ss, se, si):
	mid = (ss + se) // 2
	if ss == se:
		st[si] = arr[ss]
		return st[si]
	st[si] = min(constructSTUtil(st, arr, ss, mid, 2 * si + 1), constructSTUtil(st, arr, mid + 1, se, 2 * si + 2))
	return st[si]

def constructST(arr, n):
	h = ceil(log2(n))
	st = [0] * (2 * 2 ** h - 1)
	constructSTUtil(st, arr, 0, n - 1, 0)
	return st

def findMinUtil(st, qs, qe, ss, se, si):
	mid = (ss + se) // 2
	if qe < ss or qs > se:
		return 10000000
	if qe >= se and qs <= ss:
		return st[si]
	return min(findMinUtil(st, qs, qe, ss, mid, 2 * si + 1), findMinUtil(st, qs, qe, mid + 1, se, 2 * si + 2))

def RMQ(st, n, qs, qe):
	return findMinUtil(st, qs, qe, 0, n - 1, 0)


from math import ceil, log2, inf

class SegmentTree:

	def __init__(self, data):
		self.data = data
		n = len(data)
		height = ceil(log2(n))
		length = 2 ** (height + 1) - 1
		self.tree = [0] * length
		self.__build(0, 0, n - 1)

	def __build(self, index, start, end):
		if start == end:
			self.tree[index] = self.data[start]
			return
		mid = (start + end) // 2
		left_child_index = 2 * index + 1
		right_child_index = 2 * index + 2
		self.__build(left_child_index, start, mid)
		self.__build(right_child_index, mid + 1, end)
		self.tree[index] = min(self.tree[left_child_index], self.tree[right_child_index])

	def __query(self, index, start, end, query_start, query_end):
		if query_start > end or query_end < start:
			return inf
		if start >= query_start and end <= query_end:
			return self.tree[index]
		mid = (start + end) // 2
		left_child_index = 2 * index + 1
		right_child_index = 2 * index + 2
		return min(self.__query(left_child_index, start, mid, query_start, query_end), self.__query(right_child_index, mid + 1, end, query_start, query_end))

	def query(self, query_start, query_end):
		return self.__query(0, 0, len(self.data) - 1, query_start, query_end)

def constructST(arr, n):
	st = SegmentTree(arr)
	return st

def RMQ(st, n, qs, qe):
	return st.query(qs, qe)


class NumArray:

	def __init__(self, arr):
		self.nums = arr
		self.n = len(self.nums)
		self.seg_tree = [0] * (4 * self.n)
		self.build_tree(0, self.n - 1, 1)

	def build_tree(self, start, end, tree_node):
		if start == end:
			self.seg_tree[tree_node] = self.nums[start]
			return
		mid = (start + end) // 2
		self.build_tree(start, mid, tree_node * 2)
		self.build_tree(mid + 1, end, tree_node * 2 + 1)
		self.seg_tree[tree_node] = min(self.seg_tree[tree_node * 2], self.seg_tree[tree_node * 2 + 1])

	def query(self, start, end, tree_node, left, right):
		if start > right or end < left:
			return float('+inf')
		if start >= left and end <= right:
			return self.seg_tree[tree_node]
		mid = (start + end) // 2
		return min(self.query(start, mid, 2 * tree_node, left, right), self.query(mid + 1, end, 2 * tree_node + 1, left, right))

	def minRange(self, left: int, right: int) -> int:
		return self.query(0, self.n - 1, 1, left, right)

def constructST(arr, n):
	seg_tree = NumArray(arr)
	return seg_tree

def RMQ(seg_tree, n, left, right):
	return seg_tree.minRange(left, right)


import math
from math import ceil, log2

def constructST(arr, n):
	x = int(ceil(log2(n)))
	max_size = 2 * int(2 ** x) - 1
	tree = [0] * max_size

	def rec(ss, se, si):
		if ss == se:
			tree[si] = arr[ss]
			return arr[ss]
		mid = (ss + se) // 2
		tree[si] = min(rec(ss, mid, si * 2 + 1), rec(mid + 1, se, si * 2 + 2))
		return tree[si]
	rec(0, n - 1, 0)
	return tree

def RMQ(st, n, qs, qe):

	def rec(qs, qe, ss, se, si):
		if se < qs or ss > qe:
			return 10000000000.0
		if qs <= ss and qe >= se:
			return st[si]
		mid = (ss + se) // 2
		return min(rec(qs, qe, ss, mid, si * 2 + 1), rec(qs, qe, mid + 1, se, si * 2 + 2))
	return rec(qs, qe, 0, n - 1, 0)


def build(st, si, ss, se, arr):
	if se < ss:
		return
	elif ss == se:
		st[si] = arr[ss]
	else:
		mid = (ss + se) // 2
		build(st, 2 * si + 1, ss, mid, arr)
		build(st, 2 * si + 2, mid + 1, se, arr)
		st[si] = min(st[2 * si + 1], st[2 * si + 2])

def query(st, si, ss, se, qs, qe):
	if qs > se or qe < ss:
		return float('inf')
	elif qs <= ss and se <= qe:
		return st[si]
	else:
		mid = (ss + se) // 2
		return min(query(st, 2 * si + 1, ss, mid, qs, qe), query(st, 2 * si + 2, mid + 1, se, qs, qe))

def constructST(arr, n):
	st = [0] * (4 * n)
	build(st, 0, 0, n - 1, arr)
	return st

def RMQ(st, n, qs, qe):
	return query(st, 0, 0, n - 1, qs, qe)


def constructST(l, n):
	st = [float('inf') for _ in range(n * 4)]

	def ss(s, e, i):
		if s == e:
			st[i] = l[s]
			return
		m = (s + e) // 2
		ss(s, m, 2 * i + 1)
		ss(m + 1, e, 2 * i + 2)
		st[i] = min(st[2 * i + 1], st[2 * i + 2])
		return
	ss(0, n - 1, 0)
	return st

def RMQ(st, n, s, e):

	def ss(a, b, i):
		if a > e or b < s:
			return float('inf')
		if a >= s and b <= e:
			return st[i]
		m = (a + b) // 2
		return min(ss(a, m, 2 * i + 1), ss(m + 1, b, 2 * i + 2))
	return ss(0, n - 1, 0)
	return


def tre(t, arr, ind, lo, hi):
	if lo > hi:
		return
	if lo == hi:
		t[ind] = arr[lo]
		return
	mid = (lo + hi) // 2
	tre(t, arr, 2 * ind, lo, mid)
	tre(t, arr, 2 * ind + 1, mid + 1, hi)
	left = t[2 * ind]
	right = t[2 * ind + 1]
	t[ind] = min(left, right)

def helper(tree, ind, lo, hi, qs, qe):
	if qs > hi or qe < lo:
		return float('Inf')
	if qs <= lo and qe >= hi:
		return tree[ind]
	mid = (lo + hi) // 2
	lft = helper(tree, 2 * ind, lo, mid, qs, qe)
	rgt = helper(tree, 2 * ind + 1, mid + 1, hi, qs, qe)
	return min(lft, rgt)

def constructST(arr, n):
	t = [0] * (4 * n)
	tree = tre(t, arr, 1, 0, n - 1)
	return t

def RMQ(st, n, qs, qe):
	ans = helper(st, 1, 0, n - 1, qs, qe)
	return ans


def constructST(arr, n):
	segmentTree = [float('inf') for i in range(4 * n)]
	fillSegmentTree(arr, 0, n - 1, 0, segmentTree)
	return segmentTree

def fillSegmentTree(arr, start, end, segmentTreeIdx, segmentTree):
	if start == end:
		segmentTree[segmentTreeIdx] = arr[start]
		return
	mid = (start + end) // 2
	leftChildIdx = 2 * segmentTreeIdx + 1
	rightChildIdx = 2 * segmentTreeIdx + 2
	fillSegmentTree(arr, start, mid, leftChildIdx, segmentTree)
	fillSegmentTree(arr, mid + 1, end, rightChildIdx, segmentTree)
	segmentTree[segmentTreeIdx] = min(segmentTree[leftChildIdx], segmentTree[rightChildIdx])
	return

def RMQ(st, n, qs, qe):
	return findMinInRange(0, n - 1, qs, qe, 0, st)

def findMinInRange(start, end, left, right, currIdx, segmentTree):
	if end < left or start > right:
		return float('inf')
	if start >= left and end <= right:
		return segmentTree[currIdx]
	mid = (start + end) // 2
	leftAns = findMinInRange(start, mid, left, right, 2 * currIdx + 1, segmentTree)
	rightAns = findMinInRange(mid + 1, end, left, right, 2 * currIdx + 2, segmentTree)
	return min(leftAns, rightAns)


from math import inf

def constructST(x, n):
	dp = [inf for i in range(10001)]

	def f(i, j, k):
		if i > j:
			return inf
		if i == j:
			dp[k] = x[i]
			return x[i]
		m = (i + j) // 2
		a = f(i, m, 2 * k + 1)
		b = f(m + 1, j, 2 * k + 2)
		dp[k] = min(a, b)
		return dp[k]
	f(0, n - 1, 0)
	return dp

def RMQ(dp, n, a, b):
	mi = inf

	def f(i, j, k):
		nonlocal mi
		if j < a or b < i:
			return
		if a <= i and j <= b:
			mi = min(mi, dp[k])
			return
		m = (i + j) // 2
		f(i, m, 2 * k + 1)
		f(m + 1, j, 2 * k + 2)
	f(0, n - 1, 0)
	return mi


def constructST(arr, n):
	arr1 = [[float('inf')] * n for _ in range(n)]
	for i in range(n):
		min_ = float('inf')
		for j in range(i, n):
			min_ = min(arr[j], min_)
			arr1[i][j] = min_
	return arr1

def RMQ(st, n, qs, qe):
	return st[qs][qe]
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(i) for i in input().split()]
	Q = int(input())
	segTree = constructST(A, N)
	store = [int(i) for i in input().split()]
	ans = []
	for i in range(Q):
		(start, e) = (store[2 * i], store[2 * i + 1])
		if start > e:
			(start, e) = (e, start)
		ans.append(RMQ(segTree, N, start, e))
	print(*ans)


class SEG:

	def __init__(self, arr):
		self.n = len(arr)
		self.arr = [None] * (4 * len(arr) + 2)
		self.build_tree(arr)

	def build_tree(self, arr, ind=1, start=0, end=None):
		if end == None:
			end = self.n - 1
		if start == end:
			self.arr[ind] = arr[start]
			return
		mid = (start + end) // 2
		self.build_tree(arr, 2 * ind, start, mid)
		self.build_tree(arr, 2 * ind + 1, mid + 1, end)
		self.arr[ind] = min(self.arr[2 * ind + 1], self.arr[2 * ind])
		return

	def range_query(self, rs, re, ind=1, start=0, end=None):
		if rs > re:
			(rs, re) = (re, rs)
		if end == None:
			end = self.n - 1
		if start > re or end < rs:
			return float('inf')
		if rs <= start and end <= re:
			return self.arr[ind]
		mid = (start + end) // 2
		val1 = self.range_query(rs, re, 2 * ind, start, mid)
		val2 = self.range_query(rs, re, 2 * ind + 1, mid + 1, end)
		return min(val1, val2)

	def single_change(self, val, c, ind=1, start=0, end=None):
		if end == None:
			end = self.n - 1
		rs = val
		re = val
		if rs > end or start > re:
			return self.arr[ind]
		if rs <= start and end <= re:
			self.arr[ind] = c
			return self.arr[ind]
		mid = (start + end) // 2
		val1 = self.single_change(val, c, 2 * ind, start, mid)
		val2 = self.single_change(val, c, 2 * ind + 1, mid + 1, end)
		self.arr[ind] = min(val1, val2)
		return self.arr[ind]

def constructST(arr, n):
	return SEG(arr)

def RMQ(st, n, qs, qe):
	return st.range_query(qs, qe)
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(i) for i in input().split()]
	Q = int(input())
	segTree = constructST(A, N)
	store = [int(i) for i in input().split()]
	ans = []
	for i in range(Q):
		(start, e) = (store[2 * i], store[2 * i + 1])
		if start > e:
			(start, e) = (e, start)
		ans.append(RMQ(segTree, N, start, e))
	print(*ans)


def constructST(arr, n):
	st = [float('inf') for i in range(2 * n)]
	for i in range(n):
		st[i + n] = arr[i]
	for i in range(n - 1, 0, -1):
		st[i] = min(st[i << 1], st[i << 1 | 1])
	st[0] = st[1]
	return st

def RMQ(st, n, qs, qe):
	l = qs + n
	r = qe + n + 1
	mn = float('inf')
	while l < r:
		if l & 1:
			mn = min(st[l], mn)
			l += 1
		if r & 1:
			r -= 1
			mn = min(st[r], mn)
		l >>= 1
		r >>= 1
	return mn
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(i) for i in input().split()]
	Q = int(input())
	segTree = constructST(A, N)
	store = [int(i) for i in input().split()]
	ans = []
	for i in range(Q):
		(start, e) = (store[2 * i], store[2 * i + 1])
		if start > e:
			(start, e) = (e, start)
		ans.append(RMQ(segTree, N, start, e))
	print(*ans)


import math

def build(l, r, idx, segment, arr):
	if l == r:
		segment[idx] = arr[l]
		return
	mid = (l + r) // 2
	build(l, mid, 2 * idx + 1, segment, arr)
	build(mid + 1, r, 2 * idx + 2, segment, arr)
	segment[idx] = min(segment[2 * idx + 1], segment[2 * idx + 2])

def constructST(arr, n):
	st = [math.inf] * 4 * n
	build(0, n - 1, 0, st, arr)
	return st

def query(ss, se, idx, segment, qs, qe):
	if qs > se or qe < ss:
		return math.inf
	elif qs <= ss and qe >= se:
		return segment[idx]
	else:
		mid = (ss + se) // 2
		return min(query(ss, mid, 2 * idx + 1, segment, qs, qe), query(mid + 1, se, 2 * idx + 2, segment, qs, qe))

def RMQ(st, n, qs, qe):
	return query(0, n - 1, 0, st, qs, qe)
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(i) for i in input().split()]
	Q = int(input())
	segTree = constructST(A, N)
	store = [int(i) for i in input().split()]
	ans = []
	for i in range(Q):
		(start, e) = (store[2 * i], store[2 * i + 1])
		if start > e:
			(start, e) = (e, start)
		ans.append(RMQ(segTree, N, start, e))
	print(*ans)


def constructST(arr, n):
	tree = [0] * (n - 1 + n)
	for i in range(n):
		tree[n + i - 1] = arr[i]
	for i in range(n - 2, -1, -1):
		tree[i] = min(tree[2 * i + 1], tree[2 * i + 2])
	return tree

def RMQ(st, n, qs, qe):
	if qs > qe:
		return None
	left = n + qs - 1
	right = n + qe - 1
	result = st[left]
	while left <= right:
		if left % 2 == 0:
			result = min(result, st[left])
			left += 1
		if right % 2 == 1:
			result = min(result, st[right])
			right -= 1
		left = (left - 1) // 2
		right = (right - 1) // 2
	return result
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(i) for i in input().split()]
	Q = int(input())
	segTree = constructST(A, N)
	store = [int(i) for i in input().split()]
	ans = []
	for i in range(Q):
		(start, e) = (store[2 * i], store[2 * i + 1])
		if start > e:
			(start, e) = (e, start)
		ans.append(RMQ(segTree, N, start, e))
	print(*ans)