Range Max with Index

Sometimes you need the index of the minimum/maximum, not just the value.

Store indices in the sparse table:

st[i][0] = i  # index of min in range of length 1

for j in range(1, K):
    for i in range(n - (1 << j) + 1):
        left = st[i][j-1]
        right = st[i + (1 << (j-1))][j-1]
        st[i][j] = left if arr[left] <= arr[right] else right

Query returns the index; use it to get the value if needed.

This is useful for problems like "find the index of maximum in each query range."