Python program for the given problem
from sys import maxsize NEW_LINE from typing import List NEW_LINE INT_MAX = maxsize NEW_LINE INT_MIN = - maxsize NEW_LINE lazy = [ 0 for _ in range ( 100001 ) ] NEW_LINE