One too many

Consider a permutation $\sigma$ of $mn+1$ letters written in one line notation, say $\sigma = a_1\ldots a_{mn+1}$. An increasing subsequence of $\sigma$ is a choice of integers $i_1 <\cdots < i_k$ such that $a_{i_1}< \cdots < a_{i_k}$, a decreasing subsequence is defined analogously. Show that any permutation in $mn+1$ letters has either an increasing subsequence of length $n+1$ or a decreasing subsequence of length $m+1$. Is the bound optimal?