Hi joksy,

Here's a hint.

I think the trick is to define a partial order on as follows:

Define if

(in the usual ordering of the integers).

Think about what constitutes a chain and an antichain in this ordering (in relation to ascending or descending subsequences), then apply Dilworth's theorem, and I think you will get it.