BOJ 6549 히스토그램에서 가장 큰 직사각형 python

import sys
sys.setrecursionlimit(10**6)
def setTree(node, left, right):
    if left == right:
        tree[node] = [left, g[left]]
        return [left, g[left]]
    mid = left + (right-left)//2
    leftVal = setTree(node*2, left, mid)
    rightVal = setTree(node*2+1, mid+1, right)
    if leftVal[1] < rightVal[1]: tree[node] = [leftVal[0], leftVal[1]]
    else: tree[node] = [rightVal[0], rightVal[1]]
    return [tree[node][0], tree[node][1]]
 
def findIdx(node, start, end, left, right):
    if end < left or start > right: return -1
    if left<=start and end<=right: return tree[node]
    mid = start + (end-start)//2
    startVal = findIdx(node*2, start, mid, left, right)
    endVal = findIdx(node*2+1, mid+1, end, left, right)
    if startVal == -1: return endVal
    if endVal == -1: return startVal
    if startVal[1] > endVal[1]: return endVal
    else: return startVal
 
def find(left, right):
    idx, h = findIdx(1, 0, n-1, left, right)
    result = (right-left+1)*h
    if left <= idx-1: result = max(result, find(left, idx-1))
    if idx+1 <= right: result = max(result, find(idx+1, right))
    return result
 
while True:
    n, *g = map(int, sys.stdin.readline().split())
    if n == 0: break
    tree = [[0,0] for _ in range(n*4)]
    setTree(1, 0, n-1)
    print(find(0,n-1))