Nicest view#11749
Paris is so crowded with tourists during the Olympic games! You want to escape the city and go on a hike along a linear trail. Every kilometre on that trail, including the start and end, is marked by a milestone, which shows the stone's altitude. The slope between two consecutive milestones is constant, and no two milestones have the same altitude.
Planning to return with your friends, you try to identify the point on the hike from which you had the nicest view. The beauty of a viewpoint is defined as the distance (measured in kilometres) between your position and the previous position on your hike that had the same altitude. If such a previous position does not exist, it means you can see the city and its smog, and the beauty of that view is zero.
You have recorded the altitudes of each milestone. What is the maximal beauty value obtained during your hike?
The first line contains a single integer (1 \le n \le 10^5), the number of milestones on the trail. The second line contains integers h_1, h_2, \ldots, h_n; each h_k (0 \le h_k \le 10^6; the h_k are pairwise distinct) is the altitude (in metres) of the -th milestone along the path.
Print a single number : the maximal beauty during your hike. This number should be written as either an integer or as an irreducible fraction with d \ge 2. Recall that a fraction is irreducible if the greatest common divisor of and is .
Example 1
Example 2