Use the Sparse Table template from earlier. Optimizations for competitive programming:
Precompute LOG array to avoid log calls
Use arrays instead of dynamic lists for speed
Read input efficiently
function main():
read n, q
read array arr of size n
// Build sparse table
st = SparseTable(arr)
// Answer queries
results = empty list
for i = 0 to q - 1:
read l, r
results.append(st.query(l - 1, r - 1)) // 0-indexed
print results, one per line