n^2 + 1個の相異なる整数からなる数列には、長さn+1の増加部分列があるか、あるいは長さn+1の減少部分列があることを証明せよ。

証明：
s : a_1, a_2, …, a_{n^2+1}を相異なる整数からなる列とする。sは長さn+1の増加部分列を含まないとしよう。ここで、各a_k(k = 1, …, n^2+1)に
ラベルl_kを次の規則によってつける：各l_kはa_kから始まるsの最長増加部分列の長さとする。このとき、あるラベルl_jが存在して、sのn+1項以上が
このラベルl_jをもつことが鳩の巣原理よりわかる。ラベルl_jをもつsのn+1項以上は、減少部分列を与える。


「このとき、あるラベルl_jが存在して、sのn+1項以上がこのラベルl_jをもつことが鳩の巣原理よりわかる。」がなぜそう言えるのか分かりません。