1168. Rising or Falling Sequences

In The man who loved only numbers, Paul Hoffman gives a very absorving memoir of the brilliant number theorist Paul Erdös through the recollections of many of his collaborators, specially the mathematician Ronald L. Graham. One area were Erdös and Graham got very much involved was the Ramsey theory.

Here we take a simple example of Ramsey theory to pose a challenge to you. Consider the first 101 integers and arrange them in any order you like. No matter the arrangement, you will always be able to find 11 integers that form an increasing or a decreasing sequence. As said by Graham: “You don’t have to pick the integers consecutively. You can jump. You might pick the first one, then the thirty-eighth one - but they all have to be going up or going down”. This would not necessarily be true if you only had the first 100 integers, as it is possible to give a sequence of those 100 integers such that there is no increasing or decreasing sequence of 11 integers.

Ramsey theory generalizes this result: “to guarantee either a rising or falling sequence of length n+1, you need n2+1 numbers; with n2 numbers, you may not get it”.

Discovering such a sequence is challenging, but we invite you for a slightly bigger challenge, that is, to determine the longest rising (increasing) or falling (decreasing) sequence for a given n. It follows from the above result that the sequence has at least n+1 numbers.

Your task is to write a program to compute the longest rising or falling sequence of integers, given an arrangement of the first n2+1 integers.

You should always output the longest rising or falling sequence that appears first in the given sequence of numbers. If this rule is not enough to take a decision, then you should output the rising sequence.