AIOC Banner

Problem: Air Drop


Air Drop

Input File: dropin.txt
Output File: dropout.txt
Time Limit: 1 second

Election time is looming, and the battle for votes will be fierce. To win over the public's hearts and minds, the major parties are always looking for new and unusual methods of advertising, and this year they have hit upon a winner: the air drop.

In an air drop, the leader of the party flies over a city in an aeroplane and drops glossy leaflets onto the ground below. These leaflets fall in a straight line across the city, with the leaflets equally spaced along this line.

You are employed as the Grand Auditor, and it is your job to estimate just how much of the taxpayers' money is being spent on this exercise. Your first investigation takes you to the main street of the city, where you find eight leaflets littered along the street. These leaflets are found at positions 1, 3, 4, 7, 9, 10, 11 and 14 metres along the street as illustrated below.


Your task is to determine the largest number of leaflets that could have been dropped in a single flight. For instance, in the illustration above, a single flight could have dropped leaflets at positions 7, 9 and 11 metres along the street (since these three leaflets are equally spaced). Likewise, a single flight could have dropped leaflets at positions 3, 7 and 11 metres. However, the largest number of leaflets that could be dropped in a single flight is four, landing at positions 1, 4, 7 and 10 metres along the street.

With a frown you write a note in your little black book and move to the next street where there are even more leaflets to consider. As you watch the propaganda planes zooming overhead you realise you will be here for a long time yet; you therefore decide to write a computer program to help you with your task.


The first line of input will consist of a single integer n, giving the number of leaflets found on a particular street ( 1  <= n  <= 1000). Following this will be an additional n lines of input, each giving the position of a single leaflet, measured in metres along the street. Each of these additional n lines will contain a single integer between 1 and 10000000 inclusive. These n positions will appear in order from smallest to largest, and no two of them will be identical.


Your output file must consist of a single line containing a single integer, giving the largest number of leaflets that could have been dropped in a single flight.

Sample Input


Sample Output




Privacy statement
© Australian Mathematics Trust 2001-2019

Page generated: 24 May 2019,  3:33am AEST