Assume that we have a sequence of 17 distinct integers. Show that there exist at least 1 subsequence of 5 integers that form an increasing or decreasing sequence.

For instance, let the sequence of 17 distinct integers be

9, 13, 6, 1, 11, 7, 16, 3, 15, 10, 2, 5, 12, 4, 14, 8, 17

Then there is a increasing subsequence of length 5 in (1,3,5,8,17). There is also a decreasing subsequence of (16,15,10,5,4). Show that the statement in the second paragraph is true for all sequences of 17 distinct integers.