Ordered index range scan
Your task
Implement a simple ordered index used by a database to answer range scans. You are given a list of integer keys (possibly unsorted, possibly with duplicates) and a list of [lo, hi] range queries. Build a sorted index once, then for each query return the sorted list of keys k in the index with lo <= k <= hi, including duplicates. Keys fit in 64-bit ints; there may be up to 1e5 keys and queries. Return a list of result lists, one per query.
Examples
range_index(keys: list[int], queries: list[list[int]]) -> list[list[int]]Example 1
Input
range_index([5, 1, 3, 3, 8], [[2, 5], [3, 3], [9, 10]])Output
[[3, 3, 5], [3, 3], []]