Find Building Where Alice and Bob Can Meet

lcpy gen -n 2940   # by problem number
lcpy gen -s find_building_where_alice_and_bob_can_meet   # by problem name

Input: heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]
Output: [2,5,-1,5,2]
Explanation: In the first query, Alice and Bob can move to building 2 since heights[0] < heights[2] and heights[1] < heights[2].
In the second query, Alice and Bob can move to building 5 since heights[0] < heights[5] and heights[3] < heights[5].
In the third query, Alice cannot meet Bob since Alice cannot move to any other building.
In the fourth query, Alice and Bob can move to building 5 since heights[3] < heights[5] and heights[4] < heights[5].
In the fifth query, Alice and Bob are already in the same building.
For ans[i] != -1, It can be shown that ans[i] is the leftmost building where Alice and Bob can meet.
For ans[i] == -1, It can be shown that there is no building where Alice and Bob can meet.

Input: heights = [5,3,8,2,6,1,4,6], queries = [[0,7],[3,5],[5,2],[3,0],[1,6]]
Output: [7,6,-1,4,6]
Explanation: In the first query, Alice can directly move to Bob's building since heights[0] < heights[7].
In the second query, Alice and Bob can move to building 6 since heights[3] < heights[6] and heights[5] < heights[6].
In the third query, Alice cannot meet Bob since Bob cannot move to any other building.
In the fourth query, Alice and Bob can move to building 4 since heights[3] < heights[4] and heights[0] < heights[4].
In the fifth query, Alice can directly move to Bob's building since heights[1] < heights[6].
For ans[i] != -1, It can be shown that ans[i] is the leftmost building where Alice and Bob can meet.
For ans[i] == -1, It can be shown that there is no building where Alice and Bob can meet.

class Solution:
    # Time: O((n + q) log n) - one build pass over the tree plus a descent per query
    # Space: O(n) - segment tree over the building heights
    def leftmost_building_queries(self, heights: list[int], queries: list[list[int]]) -> list[int]:
        n = len(heights)
        size = 1
        while size < n:
            size <<= 1
        tree = [0] * (2 * size)
        tree[size : size + n] = heights
        for i in range(size - 1, 0, -1):
            tree[i] = max(tree[2 * i], tree[2 * i + 1])

        def next_greater(start: int, limit: int) -> int:
            def descend(node: int, node_lo: int, node_hi: int) -> int:
                if node_hi <= start or tree[node] <= limit:
                    return -1
                if node_lo == node_hi:
                    return node_lo
                mid = (node_lo + node_hi) // 2
                found = descend(2 * node, node_lo, mid)
                return found if found != -1 else descend(2 * node + 1, mid + 1, node_hi)

            if start >= n:
                return -1
            return descend(1, 0, size - 1)

        result: list[int] = []
        for query in queries:
            left, right = query[0], query[1]
            if left > right:
                left, right = right, left
            if left == right:
                result.append(left)
            elif heights[left] < heights[right]:
                result.append(right)
            else:
                result.append(next_greater(right, heights[left]))
        return result