Rassemblement de fête#11714
Sakurako a amis. Chacun d'eux peut être décrit par sa contribution sur la page web de programmation compétitive CodeCoders. L'ami est décrit par un nombre a_i — sa contribution.
En ce moment, parmi ces amis, l'ami connaît l'ami si et seulement si |a_i-a_j|<k. Sakurako veut rassembler autant de personnes que possible pour la fête. Cependant, il souhaite que tous soient étrangers les uns aux autres.
Formellement, s'il choisit d'inviter un ensemble de personnes \mathcal{S}=\{x_1,x_2,\dots,x_m\}, alors pour chaque i,j\in \mathcal{S} où i\neq j, la condition |a_{x_i}-a_{x_j}|\ge k doit être remplie.
Parmi tous les ensembles possibles de personnes, il veut connaître la taille du plus grand.
Malheureusement, Sakurako ne connaît pas la valeur de , donc il doit calculer la réponse pour chaque (1 \le k\le n).
La première ligne contient un entier (1\le n\le 10^6) — le nombre d'amis de Sakurako.
La deuxième ligne contient entiers a_1,\dots,a_n (-5\cdot 10^5\le a_i\le 5\cdot 10^5) — la contribution de chaque ami.
Affichez nombres. Le -ème nombre indique la plus grande taille de l'ensemble pour k = i.
Exemple
Dans le premier test :
Quand k=1, \mathcal{S}=\{1,2,3,4,6\};
Pour k=2, il peut être prouvé que le plus grand possible est \mathcal{S}=\{1,3,4,6\};
Pour k=3, k=4 et k=5, il peut être prouvé que l'un des plus grands possibles est \mathcal{S}=\{3,4,6\};
Pour k=6, il peut être prouvé que l'un des plus grands possibles est \mathcal{S}=\{1,4\}.
( points) : a_i=a_{i-1}+1 pour tout 2\le i\le n ;
( points) : -10\le a_i\le 10 ;
( points) : n\le 1000 ;
( points) : -30\le a_i\le 30 ;
( points) : sans restrictions supplémentaires.