Balanced Lineup(백준6213)

import sys 
input =sys.stdin.readline

n,q =map(int , input().split())
arr =[0]
tree= [[0,0,0] for _ in range((4*n)+1)]# 해당 수, 최소, 최대 

def init(idx,s,e):
    if s==e :
        tree[idx] = [arr[s],arr[s],arr[s]] 
        return tree[idx]
    mid =(s+e)//2 
    left= init(idx*2, s,mid)
    right = init(idx*2+1,mid+1,e) 
    tree[idx] = [0,min(tree[idx*2][1],tree[idx*2+1][1]),max(tree[idx*2][2],tree[idx*2+1][2])]
    
def maxfind(idx,l,r,s,e) :
    if( e<l   or  r  <s):
        return -1
    if(s<= l and r<=e):
        return tree[idx][2]
    mid =(l+r)//2
    return max(maxfind(idx*2,l,mid,s,e),maxfind(idx*2+1,mid+1,r,s,e))
    
def minfind(idx,l,r,s,e):
    if( e<l   or  r  <s):
        return int(1e9)
    if(s<= l and r<=e):
        return tree[idx][1]
    mid =(l+r)//2
    return min(minfind(idx*2,l,mid,s,e),minfind(idx*2+1,mid+1,r,s,e))
    





for i in range(n):
    a = int(input())
    arr.append(a)

init(1,1,n)
for i in range(q):
    a,b = map(int, input().split())
    ans = maxfind(1,1,n,a,b)-minfind(1,1,n,a,b)
    print(ans)