As pointed out in a comment by [Vladimir Dotsenko](https://mathoverflow.net/users/1306/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](http://www.numdam.org/item/CM_1935__2__463_0.pdf)); see the discussion beginning with "We solve now a similar problem" on p. 468.

In another comment [Darij Grinberg](https://mathoverflow.net/users/2530/darij-grinberg) pointed out that a generalization to possibly non-monotonic sequences was the subject of a 2012 [math overflow question](https://mathoverflow.net/questions/90128/erd%C5%91s-szekeres-for-first-differences) by [Seva](https://mathoverflow.net/users/9924/seva) which was answered by [Sergey Norin](https://mathoverflow.net/users/8733/sergey-norin).