### Problem Statement

You are given a String[] numbers containing a set of distinct non-negative integers (no leading zeroes). Let m be the smallest integer in numbers, and let M be the largest integer in numbers. An arithmetic progression of integers a+id, a+(i+1)d, ..., a+(j-1)d, a+jd is called proper if it satisfies all of the following conditions:
1. It contains at least 3 distinct integers from numbers.
2. All of the numbers in the progression are integers between m and M, inclusive.
3. If it were extended in either direction, condition 2 would no longer be satisfied. In other words, neither a+(i-1)d nor a+(j+1)d are between m and M, inclusive. (See example 0 for further clarification.)
Given a proper arithmetic progression, let a be the number of integers in the progression that are contained in numbers, and let b be the total number of integers in the progression. The aptitude of the progression is defined as a divided by b. Given numbers, return the maximal aptitude of a proper arithmetic progression as a String[] containing exactly 2 elements representing 2 integers (with no leading zeroes), first of which divided by the second equals the maximal aptitude. The first and the second elements of String[] you return must represent non-negative integers which do not have common divisors greater than 1. Return {"0", "1"} if no proper arithmetic progression exists.

### Definition

 Class: ArithmeticProgressions Method: maxAptitude Parameters: String[] Returns: String[] Method signature: String[] maxAptitude(String[] numbers) (be sure your method is public)

### Constraints

-numbers will contain between 1 and 50 elements, inclusive.
-Each element of numbers will contain between 1 and 18 characters, inclusive.
-Each character of every element of numbers will be a digit ('0'-'9').
-No element of numbers will contain '0' (zero) as its first character.
-All elements of numbers will be distinct.

### Examples

0)

 `{"1", "3", "5", "8"}`
`Returns: {"3", "4" }`
 We have two proper arithmetic progressions here: 1, 2, 3, 4, 5, 6, 7, 8 and 1, 3, 5, 7. Both of them can not be extended since neither 0, nor 9 lies in [1; 8] in the first case and neither -1, nor 9 lies in [1; 8] in the second case. 4 elements of the first progression belong to numbers and so its aptitude is 4/8 = 1/2. 3 elements of the second progression belong to numbers and so its aptitude is 3/4, which is highest possible in this case.
1)

 `{"1", "3", "5", "7", "9", "11", "13", "15", "17", "19"}`
`Returns: {"1", "1" }`
 The elements of numbers form a proper arithmetic progression, hence its aptitude is 1.
2)

 `{"1", "999999999999999999"}`
`Returns: {"0", "1" }`
 There are not enough elements in numbers to form a proper arithmetic progression.
3)

 `{"1", "7", "13", "3511", "1053", "10", "5"}`
`Returns: {"3", "391" }`
 The elements of numbers are not necessarily sorted.

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7856

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10780&pm=7856

Xixas

#### Testers:

PabloGilberto , Yarin , Olexiy , ivan_metelsky

Math, Search