Building a tree with the heap property from an array and preserving its order

How efficiently can I build a binary tree satisfying the heap property from an array and such that the inorder traversal of the tree is the original array?

For example, if I have:


2 1 5 6 2 3

I want to build:

1
 / \
2   2
   / \
  5   3
   \
    6

Because it has the heap property and its inorder is the original array 2 1 5 6 2 3.

An O(n)-time algorithm for the problem has been published by Gabow et al. (1984) in the context of "Cartesian trees": https://dl.acm.org/doi/10.1145/800057.808675

As pointed out above by Raphael, there is a close relationship to treaps.
You may also want to visit the corresponding Wikipedia entry: https://en.wikipedia.org/wiki/Cartesian_tree

StackExchange Computer Science Q#66327, answer score: 2