Write a program which manipulates a sequence $A = \\{a_0, a_1, ..., a_{n-1}\\}$ by the following operations:

* min($b, e$): report the minimum element in $a_b, a_{b+1}, ..., a_{e-1}$
* max($b, e$): report the maximum element in $a_b, a_{b+1}, ..., a_{e-1}$

Constraints

* $1 \leq n \leq 1,000$
* $-1,000,000,000 \leq a_i \leq 1,000,000,000$
* $1 \leq q \leq 1,000$
* $0 \leq b < e \leq n$

Input

The input is given in the following format.


$n$
$a_0 \; a_1, ..., \; a_{n-1}$
$q$
$com_1 \; b_1 \; e_1$
$com_2 \; b_2 \; e_2$
:
$com_{q} \; b_{q} \; e_{q}$


In the first line, $n$ (the number of elements in $A$) is given. In the second line, $a_i$ (each element in $A$) are given. In the third line, the number of queries $q$ is given and each query is given in the following $q$ lines. $com_i$ denotes a type of query. 0 and 1 represents min($b, e$) and max($b, e$) respectively.

Output

For each query, print the minimum element or the maximum element in a line.

Example

Input

7
8 3 7 1 9 1 4
3
0 0 3
0 1 5
1 0 7


Output

3
1
9

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
for _ in range(Q):
	q = list(map(int, input().split()))
	if q[0] == 0:
		print(min(A[q[1]:q[2]]))
	else:
		print(max(A[q[1]:q[2]]))


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(com, b, e) = map(int, input().split())
	if com == 0:
		if b == e - 1:
			print(a[e - 1])
		else:
			print(min(a[b:e]))
	if com == 1:
		if b == e - 1:
			print(a[e - 1])
		else:
			print(max(a[b:e]))


from functools import reduce
from collections import deque
import sys
input = sys.stdin.readline

def main():
	n = int(input())
	l = list(map(int, input().split()))
	for i in range(int(input())):
		(a, n1, n2) = map(int, input().split())
		if a == 0:
			min = reduce(lambda a, b: a if a < b else b, l[n1:n2])
			print(min)
		elif a == 1:
			max = reduce(lambda a, b: a if a > b else b, l[n1:n2])
			print(max)
main()


def main():
	input()
	a = [int(x) for x in input().split(' ')]
	q = int(input())
	for i in range(q):
		(cmd, b, e) = [int(x) for x in input().split(' ')]
		if cmd == 0:
			print(min(a[b:e]))
		else:
			print(max(a[b:e]))
main()


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(com, b, e) = map(int, input().split())
	if com == 0:
		print(min(a[b:e]))
	else:
		print(max(a[b:e]))


n = int(input())
A = [int(a) for a in input().split()]
for _ in range(int(input())):
	(com, b, e) = input().split()
	if com == '0':
		print(min(A[int(b):int(e)]))
	else:
		print(max(A[int(b):int(e)]))


n = int(input())
nums = list(map(int, input().split(' ')))
q = int(input())
for i in range(q):
	op = list(map(int, input().split(' ')))
	if op[0] == 0:
		min = float('inf')
		for num in nums[op[1]:op[2]]:
			if num < min:
				min = num
		print(min)
	elif op[0] == 1:
		max = -float('inf')
		for num in nums[op[1]:op[2]]:
			if num > max:
				max = num
		print(max)


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(com, b, e) = map(int, input().split())
	if com == 0:
		mn = min(a[b:e])
		print(mn)
	else:
		mx = max(a[b:e])
		print(mx)


import sys
sys.stdin.readline()
a = list(map(int, sys.stdin.readline().split()))
f = [min, max]
for _ in range(int(sys.stdin.readline())):
	(c, b, e) = map(int, sys.stdin.readline().split())
	print(f[c](a[b:e]))


n = int(input())
A = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(a, b, c) = map(int, input().split())
	if a == 0:
		print(min(A[b:c]))
	else:
		print(max(A[b:c]))


n = int(input())
A = [int(x) for x in input().split()]
q = int(input())
for i in range(q):
	(com, b, e) = [int(x) for x in input().split()]
	if com:
		print(max(A[b:e]))
	else:
		print(min(A[b:e]))


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(com, b, e) = map(int, input().split())
	if com == 0:
		print(min(a[b:e]))
	else:
		print(max(a[b:e]))


n = int(input())
box = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	(a, b, c) = map(int, input().split())
	if a == 0:
		print(min(box[b:c]))
	else:
		print(max(box[b:c]))


num_int = int(input())
numbers = list(map(lambda x: int(x), input().split()))
num_query = int(input())
for _ in range(num_query):
	(op, begin, end) = map(lambda x: int(x), input().split())
	sub_numbers = numbers[begin:end]
	if 0 == op:
		min_num = min(sub_numbers)
		print(min_num)
	elif 1 == op:
		max_num = max(sub_numbers)
		print(max_num)


n = int(input())
A = list(map(int, input().split()))
q = int(input())
Q = list()
for i in range(q):
	tmp = list(map(int, input().split()))
	Q.append(tmp)
for query in Q:
	if query[0] == 0:
		print(min(A[query[1]:query[2]]))
	else:
		print(max(A[query[1]:query[2]]))


import sys
input()
arr = list(map(int, input().split()))
qn = int(input())
queries = sys.stdin.readlines()
for i in range(qn):
	(com, b, c) = queries[i].split()
	if com == '0':
		print(min(arr[int(b):int(c)]))
	elif com == '1':
		print(max(arr[int(b):int(c)]))
	else:
		raise AssertionError


def resolve():
	input()
	A = [int(i) for i in input().split()]
	Q = int(input())
	for _ in range(Q):
		q = [int(i) for i in input().split()]
		if q[0] == 0:
			print(min(A[q[1]:q[2]]))
		else:
			print(max(A[q[1]:q[2]]))
resolve()


def run():
	n = int(input())
	li = [int(x) for x in input().split()]
	assert len(li) == n
	q = int(input())
	for _ in range(q):
		(com, b, e) = [int(x) for x in input().split()]
		if com == 0:
			print(min(li[b:e]))
		elif com == 1:
			print(max(li[b:e]))
		else:
			raise ValueError('invalid command')
run()


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(x, y, z) = map(int, input().split())
	if x == 0:
		print(min(a[y:z]))
	else:
		print(max(a[y:z]))


n = int(input())
A = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	(com, b, e) = map(int, input().split())
	if com == 0:
		print(min(A[b:e]))
	elif com == 1:
		print(max(A[b:e]))
	else:
		raise


n = int(input())
A = list(map(int, input().split()))
q = int(input())
for i in range(q):
	query = list(map(int, input().split()))
	if query[0] == 0:
		print(min(A[query[1]:query[2]]))
	else:
		print(max(A[query[1]:query[2]]))


n = int(input())
l = list(map(int, input().split()))
q = int(input())
for i in range(q):
	a = input().split()
	b = int(a[1])
	c = int(a[2])
	if a[0] == '0':
		print(min(l[b:c]))
	else:
		print(max(l[b:c]))


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(order, b, e) = map(int, input().split())
	if order == 0:
		print(min(a[b:e]))
	else:
		print(max(a[b:e]))


input()
nums = list(map(int, input().split(' ')))
r = input()
for _ in range(int(r)):
	(mx, f, l) = list(map(int, input().split(' ')))
	if mx:
		print(max(nums[f:l]))
	else:
		print(min(nums[f:l]))


n = int(input())
A = list(map(int, input().split()))
n2 = int(input())
for i in range(n2):
	(com, b, e) = map(int, input().split())
	if com == 0:
		print(min(A[b:e]))
	else:
		print(max(A[b:e]))


n = int(input())
num = list(map(int, input().split()))
q = int(input())
for i in range(q):
	query = list(map(int, input().split()))
	flag = query[0]
	start = query[1]
	end = query[2]
	if flag == 0:
		print(min(num[start:end]))
	elif flag == 1:
		print(max(num[start:end]))


N = int(input())
X = list(map(int, input().split()))
q = int(input())
for i in range(q):
	a = input().split()
	t = int(a[1])
	s = int(a[2])
	if a[0] == '0':
		print(min(X[t:s]))
	elif a[0] == '1':
		print(max(X[t:s]))


n = int(input())
a = list(map(int, input().split(' ')))
q = int(input())
for i in range(q):
	(c, b, e) = map(int, input().split(' '))
	if c:
		print(max(a[b:e]))
	else:
		print(min(a[b:e]))


n = int(input())
A = list(map(int, input().split()))
m = int(input())
for _ in range(m):
	(a, b, c) = map(int, input().split())
	if a == 0:
		print(min(A[b:c]))
	else:
		print(max(A[b:c]))


from sys import stdin
n = int(stdin.readline())
l = list(map(int, stdin.readline().split()))
num = int(stdin.readline())
for i in range(num):
	inp = list(stdin.readline().split())
	start = int(inp[1])
	end = int(inp[2])
	if inp[0] == '0':
		print(min(l[start:end]))
	else:
		print(max(l[start:end]))


n = int(input())
A = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(com, b, e) = list(map(int, input().split()))
	if com == 0:
		print(min(A[b:e]))
	else:
		print(max(A[b:e]))


def main():
	n = int(input())
	l = list(map(int, input().split(' ')))
	q = int(input())
	for v in range(q):
		i = list(map(int, input().split(' ')))
		if i[0] == 0:
			print(min(l[i[1]:i[2]]))
		if i[0] == 1:
			print(max(l[i[1]:i[2]]))
main()


input()
A = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	query = list(map(int, input().split()))
	if query[0] == 0:
		print(min(A[query[1]:query[2]]))
	else:
		print(max(A[query[1]:query[2]]))


def minbe(b, e):
	B = A[b:e]
	print(min(B))

def maxbe(b, e):
	B = A[b:e]
	print(max(B))
n = int(input())
A = list(map(int, input().split()))
q = int(input())
for i in range(q):
	queryi = list(map(int, input().split()))
	if queryi[0] == 0:
		minbe(queryi[1], queryi[2])
	else:
		maxbe(queryi[1], queryi[2])


readline = open(0).readline
writelines = open(1, 'w').writelines
N = int(readline())
A = map(int, readline().split())
N0 = 2 ** (N - 1).bit_length()
D1 = [0] * (2 * N0)
D2 = [0] * (2 * N0)
for (i, a) in enumerate(A):
	D1[i + N0 - 1] = D2[i + N0 - 1] = a
for i in range(N0 - 2, -1, -1):
	D1[i] = min(D1[2 * i + 1], D1[2 * i + 2])
	D2[i] = max(D2[2 * i + 1], D2[2 * i + 2])

def query_min(l, r):
	L = l + N0
	R = r + N0
	s = 1000000000.0
	while L < R:
		if R & 1:
			R -= 1
			s = min(s, D1[R - 1])
		if L & 1:
			s = min(s, D1[L - 1])
			L += 1
		L >>= 1
		R >>= 1
	return s

def query_max(l, r):
	L = l + N0
	R = r + N0
	s = -1000000000.0
	while L < R:
		if R & 1:
			R -= 1
			s = max(s, D2[R - 1])
		if L & 1:
			s = max(s, D2[L - 1])
			L += 1
		L >>= 1
		R >>= 1
	return s
C = [query_min, query_max].__getitem__
Q = int(readline())
ans = []
for q in range(Q):
	(t, b, e) = map(int, readline().split())
	ans.append('%d\n' % C(t)(b, e))
writelines(ans)


n = int(input())
arr = [*map(int, input().split())]
q = int(input())
while q:
	q -= 1
	(op, l, r) = map(int, input().split())
	if op == 0:
		print(min(arr[l:r]))
	else:
		print(max(arr[l:r]))


def solve():
	from sys import stdin
	f_i = stdin
	n = f_i.readline()
	A = list(map(int, f_i.readline().split()))
	q = int(f_i.readline())
	ans = []
	for i in range(q):
		(com, b, e) = map(int, f_i.readline().split())
		if com == 0:
			ans.append(str(min(A[b:e])))
		else:
			ans.append(str(max(A[b:e])))
	print('\n'.join(ans))
solve()


def query(tree, begin, end, target, left, right, infinity, func):
	if right <= begin or end <= left:
		return infinity
	if begin <= left and right <= end:
		return tree[target]
	next_position = (left + right) // 2
	left_index = 2 * target + 1
	right_index = left_index + 1
	left_side_value = query(tree, begin, end, left_index, left, next_position, infinity, func)
	right_side_value = query(tree, begin, end, right_index, next_position, right, infinity, func)
	return func(left_side_value, right_side_value)
over_value = 2000000000
ary_size = int(input())
data_ary = list(map(int, input().split()))
leaf_size = 1
while leaf_size < ary_size:
	leaf_size = leaf_size * 2
tree_size = leaf_size * 2 - 1
min_tree = [over_value] * tree_size
max_tree = [-over_value] * tree_size
for i in range(ary_size):
	index = leaf_size - 1 + i
	min_tree[index] = data_ary[i]
	max_tree[index] = data_ary[i]
for i in range(leaf_size - 2, -1, -1):
	left_index = 2 * i + 1
	right_index = left_index + 1
	min_tree[i] = min(min_tree[left_index], min_tree[right_index])
	max_tree[i] = max(max_tree[left_index], max_tree[right_index])
query_size = int(input())
for i in range(query_size):
	input_data = list(map(int, input().split()))
	command = input_data[0]
	begin = input_data[1]
	end = input_data[2]
	if command == 0:
		min_value = query(min_tree, begin, end, 0, 0, leaf_size, over_value, min)
		print(min_value)
	elif command == 1:
		max_value = query(max_tree, begin, end, 0, 0, leaf_size, -over_value, max)
		print(max_value)


import sys
n = int(input())
a = list(map(int, input().split()))
q = int(input())
for query in (line.split() for line in sys.stdin):
	query = list(map(int, query))
	if query[0] == 0:
		print(min(a[query[1]:query[2]]))
	else:
		print(max(a[query[1]:query[2]]))


n = int(input())
A = list(map(int, input().split()))
q = int(input())
for i in range(q):
	com = list(map(int, input().split()))
	if com[0] == 0:
		print(min(A[com[1]:com[2]]))
	else:
		print(max(A[com[1]:com[2]]))


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(c, b, e) = list(map(int, input().split()))
	if c == 0:
		print(min(a[b:e]))
	else:
		print(max(a[b:e]))


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	tmp = list(map(int, input().split()))
	if tmp[0] == 0:
		ans = float('inf')
		for j in range(tmp[1], tmp[2]):
			ans = min(ans, a[j])
		print(ans)
	else:
		ans = float('inf') * -1
		for j in range(tmp[1], tmp[2]):
			ans = max(ans, a[j])
		print(ans)


def main():
	param = input()
	param = input().split(' ')
	seq = [int(a) for a in param]
	n = int(input())
	for _ in range(n):
		param = input().split(' ')
		if param[0] == '0':
			print(min(seq[int(param[1]):int(param[2])]))
		elif param[0] == '1':
			print(max(seq[int(param[1]):int(param[2])]))
main()


n = input()
l = list(map(int, input().split()))
n = int(input())
for i in range(n):
	q = list(map(int, input().split()))
	li = l[q[1]:q[2]]
	if q[0] == 0:
		print(min(li))
	else:
		print(max(li))


input()
a = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	(x, s, t) = list(map(int, input().split()))
	print(min(a[s:t]) if x == 0 else max(a[s:t]))


N = int(input())
A = list(map(int, input().split()))
Q = int(input())
for i in range(Q):
	(qtype, b, e) = map(int, input().split())
	if qtype == 0:
		print(min(A[b:e]))
	elif qtype == 1:
		print(max(A[b:e]))


n = int(input())
a = list(map(int, input().split()))
for i in range(int(input())):
	l = list(map(int, input().split()))
	if l[0]:
		print(max(a[l[1]:l[2]]))
	else:
		print(min(a[l[1]:l[2]]))


n = int(input())
num = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	query = list(map(int, input().split()))
	flag = query[0]
	start = query[1]
	end = query[2]
	if flag == 0:
		print(min(num[start:end]))
	elif flag == 1:
		print(max(num[start:end]))


input()
listnum = list(map(int, input().split()))
for i in range(int(input())):
	eachq = list(map(int, input().split()))
	if eachq[0] == 0:
		print(min(listnum[eachq[1]:eachq[2]]))
	elif eachq[0] == 1:
		print(max(listnum[eachq[1]:eachq[2]]))


n = int(input())
s = list(map(int, input().split()))
m = int(input())
for i in range(m):
	(a, b, c) = map(int, input().split())
	if a == 0:
		d = min(s[b:c])
	else:
		d = max(s[b:c])
	print(d)


num = input()
L = list(map(int, input().split()))
n = int(input())
for _ in range(n):
	(c, b, e) = [int(x) for x in input().split()]
	if c == 0:
		print(min(L[b:e]))
	elif c == 1:
		print(max(L[b:e]))