As pointed out in a comment by Vladimir Dotsenko, the problem I asked about was posed and solved in the classical paper by Erdős and Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463–470 (pdf); see the discussion beginning with "We solve now a similar problem" on p. 468.
In another comment Darij Grinberg pointed out that a generalization to possibly non-monotonic sequences was the subject of a 2012 math overflow question by Seva which was answered by Sergey Norin.