Cho dãy \(a\) gồm \(n\) số nguyên dương phân biệt.

Một dãy số nguyên dương \(p_1, p_2, ..., p_k\) được định nghĩa là đẹp nếu nó thỏa mãn tính chất sau:

• \(k ≥ 1\)

• \(1 ≤ p_1 < p_2 < ... < p_k < n\)

• Tồn tại một số nguyên dương \(m ≥ 2\) thỏa mãn \(a_{p1} ≡ a_{p2} ≡ ... ≡ a_{pk} mod (m)\).

Yêu cầu: Hãy tìm dãy đẹp dài nhất có thể.

Input

• Dòng đầu gồm số nguyên dương \( n ( n ≤ 10^5\)).

• Dòng thứ hai gồm \(n\) số nguyên dương miêu tả dãy \(a\) (\(a_i ≤ 10^12\)).

• Dữ liệu đảm bảo rằng dãy \(a\) gồm các số phân biêt.

Output

• In ra một dòng gồm hai số \(k\) và \(m\) lần lượt là độ dài của dãy lớn nhất tìm được và số \(m\) thỏa mãn.

Subtask

• 10% số test có \( n ≤ 10\)

• 20% số test có \( a_i ≤ 100\)

• 30% số test có \( n ≤ 50\)

• 40% số test còn lại không có ràng buộc gì thêm.

Sample INput 1

5
1 5 2 4 6

Sample Output 1

3 2

Sample Input 2

7
2 5 3 8 6 11 14

Sample Output 2

5 3