Use the Sparse Table template from earlier. Key optimizations for competitive programming:
Precompute LOG array to avoid log calls
Use arrays instead of lists for speed
Read input efficiently (in Python, use sys.stdin)
import sys
from math import log2
def main():
input = sys.stdin.readline
n, q = map(int, input().split())
arr = list(map(int, input().split()))
# Build sparse table
st = SparseTable(arr)
# Answer queries
results = []
for _ in range(q):
l, r = map(int, input().split())
results.append(st.query(l-1, r-1)) # 0-indexed
print('\n'.join(map(str, results)))