Maximal Congruent Subset Problem

Given an integer sequence \(a_1, a_2, \ldots, a_n\), the task is to choose an integer modulus \(m\) (with \(m \ge 2\)) and select a subset of \(k\) elements from the sequence such that all chosen elements have the same remainder when divided by \(m\). In other words, there exists a remainder \(r\) (\(0 \le r < m\)) for which each of the selected numbers satisfies \(a_i \equiv r \pmod{m}\).

Your objective is to:

1. Maximize \(k\), the number of selected elements.
2. Under the condition of achieving the maximum \(k\), choose the largest possible \(m\) that attains that \(k\).

Note: If all elements can be grouped with the same remainder for many \(m\), then choose the maximum \(m\) within the search range. For implementation, let the search range for \(m\) be \(m \in [2, L]\) where \(L = \max(a) - \min(a) + 1\) or 100, whichever is larger.

The answer should output two integers separated by a space: the maximum \(k\) and the chosen modulus \(m\).

All formulas are expressed in \(\LaTeX\) format.

inputFormat

The first line contains an integer \(n\) (the length of the sequence). The second line contains \(n\) space-separated integers representing the sequence \(a_1, a_2, \ldots, a_n\).

outputFormat

Output two integers: \(k\) and \(m\), where \(k\) is the maximum number of elements that are congruent modulo \(m\) and \(m\) is the largest modulus (\(\ge 2\)) for which this maximum frequency is achieved.

sample

5
1 2 3 4 5

3 2