Party gathering#11714
Sakurako has friends. Each of them can be described by their contribution on the competitive programming web-page CodeCoders. Friend is described by a number a_i — his contribution.
Right now, among these friends, friend is familiar with friend if and only if |a_i-a_j| < k. Sakurako wants to gather as many people as possible to the party. However, he wants all of them to be unfamiliar with each other.
Formally, if he chooses to invite a set of people \mathcal{S} = \{x_1, x_2, \dots, x_m\}, then for every i, j \in \mathcal{S} where i \neq j, the condition |a_{x_i} - a_{x_j}| \ge k must be fulfilled.
Out of all possible sets of people, he wants to know the size of the largest one.
Unfortunately, Sakurako doesn't know the value of , so he has to compute the answer for each (1 \le k \le n).
The first line contains one integer (1 \le n \le 10^6) — the number of Sakurako's friends.
The second line contains integers a_1, \dots, a_n (-5 \cdot 10^5 \le a_i \le 5 \cdot 10^5) — the contribution of each friend.
Output numbers. The -th number denotes the largest size of set for k = i.
Example
In the first test:
When k = 1, \mathcal{S} = \{1, 2, 3, 4, 6\};
For k = 2, it can be proven that the largest possible is \mathcal{S} = \{1, 3, 4, 6\};
For k = 3, k = 4, and k = 5, it can be proven that one of the largest possible is \mathcal{S} = \{3, 4, 6\};
For k = 6, it can be proven that one of the largest possible is \mathcal{S} = \{1, 4\}.
(6 points): a_i = a_{i-1} + 1 for all 2 \le i \le n;
(14 points): -10 \le a_i \le 10;
(41 points): n \le 1000;
(77 points): -30 \le a_i \le 30;
(112 points): without additional restrictions.