Find Building Where Alice and Bob Can Meet

export function leftmostBuildingQueries(heights: number[], queries: number[][]): number[] {
  const [n, q] = [heights.length, queries.length];
  const answer: number[] = new Array(q).fill(-1);
  const newQueries: number[][][] = Array.from({ length: n }, () => []);
  queries.forEach(([a, b], i) => {
    [a, b] = a < b ? [a, b] : [b, a];
    if (a === b || heights[a] < heights[b]) {
      answer[i] = b;
    } else {
      newQueries[b].push([heights[a], i]);
    }
  });
 
  const stack: number[][] = [];
  for (let i = n - 1; 0 <= i; i--) {
    const stackSize = stack.length;
    for (const [a, b] of newQueries[i]) {
      const position = search(stack, a);
      if (position < stackSize && 0 <= position) {
        answer[b] = stack[position][1];
      }
    }
    while (0 < stack.length && stack[stack.length - 1][0] <= heights[i]) {
      stack.pop();
    }
    stack.push([heights[i], i]);
  }
  return answer;
}
 
function search(stack: number[][], target: number): number {
  let [left, right] = [0, stack.length - 1];
  let result = -1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (target < stack[mid][0]) {
      result = Math.max(result, mid);
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return result;
}