Indian National Olympiad in Informatics

Related:

Online Programming Contest, 6-7 August 2005

IARCS home > OLYMPIAD

Advanced Division

Problem 1: The Sculptor, (K Narayan Kumar, CMI)

As we all know, Indraneel is a talented painter. A less known fact is that Indraneel also dabbles in modern sculpture. Recently, he has taken a fancy to protecting the environment, recycling junk etc. Since then, he has been using only recycled material in his sculptures.

The construction work at the site for the new campus for the Chennai Mathematical Institute has generated its own pile of junk. Among this junk are a large number of steel rods of varying lengths. Indraneel plans to use some of these in his new sculpture to be placed at the entrance, which will consist of a sequence of steel rods placed upright in a line. However, he wants the rods to be arranged in increasing order of height and, further, demands that the difference in height between each pair of adjacent rods be the same. Your task is you help him identify the largest set of rods that can be used in his sculpture.

For example, if there are 5 rods of lengths 3, 2, 7, 11 and 6, then the desired set consists of the three rods of lengths 3, 7 and 11.

Input format

The first line of the input consists of a single integer N indicating the number of rods. This is followed by a single line consisting of N integers indicating the lengths of the N rods.

Output format

The first line of the output consists of a single integer M indicating the maximum number of rods from this collection that may be used in Indraneel's sculpture. This is followed by a single line containing M integers indicating the lengths of the rods in a sculpture with M rods, in ascending order. If there is more than one such solution then it suffices to print out one.

Test Data:

You may assume that 1 ≤ N ≤ 2000.

Example:

Here is the sample input and output corresponding to the example discussed above.

Sample Input

5
3 2 7 11 6

Sample Output

3
3 7 11