Cặp quà gần nhau

Trong dịp Giáng sinh, xưởng đồ chơi của ông già Noel đang gấp rút chuẩn bị các món quà gửi đi khắp nơi.
Có \(n\) món quà, mỗi món có mã số \(a_i\) (\(1 \le i \le n\)). Một số mã có thể trùng nhau vì quà giống nhau được sản xuất nhiều lần.

Gọi \(f(x)\) là số lần xuất hiện của món quà có mã số \(x\) trong danh sách. Hai mã quà \(x\) và \(y\) \((x \ne y)\) được coi là gần nhau nhất nếu chênh lệch giữa số lần xuất hiện của chúng là nhỏ nhất, tức:
$
|f(x) - f(y)| \text{ là nhỏ nhất có thể.}
$
Vì là một người vô cùng tâm huyết với nghề nên ông rất cẩn thận đánh giá các món quà ông chuẩn bị. Ông muốn chênh lệch trên là nhỏ nhất có thể.

Lưu ý: với các mã quà \(i\) không xuất hiện trong dãy, hay \(f(i)=0\), ta sẽ không xét đến.

Yêu cầu:
Tìm và in ra chênh lệch nhỏ nhất trên.

Input

• Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 10^5\)).

• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^6\)).

Output

In ra kết quả của bài toán

Scoring

• Có \(50\%\) số điểm ứng với \(n \le 1000\).

Sample Input 1

9
1 2 3 3 3 4 4 4 4

Sample Output 1

0