Problem:

Min-Max Element

 

  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}$

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.

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$

Sample Input 1

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

Sample Output 1

3
1
9



Sample input:
7
8 3 7 1 9 1 4
3
0 0 3
0 1 5
1 0 7


Sample output:
3
1
9

Submission status: Wrong Answer

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:

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')


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
# coding=utf-8

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]))

Submission status: Accepted

Solution code:
# AOJ ITP2_3_B: Min-Max Element
# Python3 2018.6.24 bal4u

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]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:

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)

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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]]))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:

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]))

Submission status: Accepted

Solution code:

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]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()))

    # min
    if com == 0:
        print(min(A[b:e]))

    # max
    else:
        print(max(A[b:e]))

Submission status: Accepted

Solution code:
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]]))

Submission status: Accepted

Solution code:
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]]))

Submission status: Accepted

Solution code:
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]]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:

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()

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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]]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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] ))

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Basic Operations - Min-Max Element
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_3_B&lang=jp

"""

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)]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
if __name__ == '__main__':

	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]))

Submission status: Accepted

Solution code:
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:
        # min(b,e)
        print(min(A[b:e]))
    elif com == 1:
        # max(b,e)
        print(max(A[b:e]))
    else:
        raise

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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]]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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]]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_3_B&lang=jp
# Min-Max Element

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)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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 = 1e9
    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 = -1e9
    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)

Submission status: Accepted

Solution code:
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]]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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]))

Submission status: Runtime Error

Solution code:
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)