1168. Rising or Falling Sequences

单点时限: 2.0 sec

内存限制: 256 MB

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.

输入格式

The input is composed by the integer value of n (0 < n ≤ 100) in the first line, followed by n^2+1 different integers, each in a separate line, comprehended between 1 and n^2+1.

输出格式

Your output should be the first longest rising or falling sequence of integers, from the arrangement given as input, considering the rules above. Each number in the sequence should be printed in a separate line.

样例

Input
3
5
6
3
2
9
1
8
4
7
10
Output
5
6
9
10

5 人解决,5 人已尝试。

7 份提交通过,共有 8 份提交。

5.7 EMB 奖励。

创建: 15 年,6 月前.

修改: 5 年,3 月前.

最后提交: 2 年前.

来源: partychen

题目标签