The Erdos-Szekeres theorem says that every $n$-permutation $p(1), p(2), \ldots, p(n)$ has either an increasing run or a decreasing run of length $\sqrt n$, where an increasing run is
$p(i\_1) < p(i\_2) < \cdots < p(i\_m)$ for $i\_1 < i\_2 < \cdots < i\_m$,
and a decreasing run is defined similarly.
Call $i\_m-i\_1+1$ the"width" of the run.
It is easy to construct examples showing that the theorem is tight. For example, for $n=16$,
$4, 3, 2, 1, 8, 7, 6, 5, 12, 11, 10, 9, 16, 15, 14, 13.$
Here no run has length more than $4$.
However, in this construction there are runs of very small width.
I'm looking for a construction for general $n$ in which: (a) there are no increasing or decreasing runs of length larger than $O(\sqrt n)$; and (b) every run of length $\Omega(\sqrt n)$ has large width (as large as possible).



Looking for construction related to Erdos-Szekeres theorem
These runs are strongly related to Young tableaux. So it is the best to first make a tableau that has the corresponding property. This we can construct by induction: Start with 1, then make a copy of it +1 and put it below, then copy it +2 and put it right from it. So you should get:
$\begin{array}{cc}
1&3\cr
2&4\cr
\end{array}$.
After repeating it on, we get 
$\begin{array}{cccc}
1&3&9&11\cr
2&4&10&12\cr
5&7&13&15\cr
6&8&14&16\cr
\end{array}$ and so on.


To make a sequence of this, first take the last row of the tableau, then the last but one and so on, so you should get $6, 8, 14, 16, 5, 7, 13, 15, 2, 4, 10, 12, 1, 3, 9, 11$. Now, without giving a formal proof, any long enough run must skip over two correspondingly big "breaks" in the matrix which will make it have a large width. Unless I am mistaken, a run of length $c\sqrt n$ should have width $\Omega(c n)$.


Update: I was mistaken, as pointed out by Aaron, so the width should be smaller.


