$\newcommand{\N}{\mathbb{N}}\newcommand{\Z}{\mathbb{Z}}\newcommand{\R}{\mathbb{R}}\DeclareMathOperator{\E}{E}$

This problem appears on Page 21 of the geometric range searching survey by Agarwal and Erickson.

What is the fastest algorithm for partitioning a sequence $x_1,\ldots,x_n$ of $n$ comparable numbers into $O(\sqrt{n})$ monotonic subsequences.

The Erdős–Szekeres Theorem implies that this problem has a solution. Bar-Yehuda and Fogel show that this problem can be solved in $O(n^{3/2})$ time. Is there a near-linear time algorithm?