Cartesian Tree — Range Minimum via Tree Structure

Node build(int[] arr) {
  Deque stack = new ArrayDeque<>();
  Node root = null;
  for (int x : arr) {
    Node n = new Node(x);
    Node last = null;
    while (!stack.isEmpty() && stack.peek().val > x) last = stack.pop();
    n.left = last;
    if (!stack.isEmpty()) stack.peek().right = n;
    else root = n;
    stack.push(n);
  }
  return root;
}