Reunión de amigos#11714
Sakurako tiene amigos. Cada uno de ellos puede ser descrito por su contribución en la página web de programación competitiva CodeCoders. El amigo está descrito por un número a_i — su contribución.
En este momento, dentro de estos amigos, el amigo está familiarizado con el amigo si y solo si |a_i-a_j|<k. Sakurako quiere reunir a la mayor cantidad de personas posible para la fiesta. Sin embargo, quiere que todos ellos sean desconocidos entre sí.
Formalmente, si elige invitar a un conjunto de personas \mathcal{S}=\{x_1,x_2,\dots,x_m\}, entonces para cada i,j\in \mathcal{S} donde i\neq j, se debe cumplir la condición |a_{x_i}-a_{x_j}|\ge k.
De todos los posibles conjuntos de personas, quiere saber el tamaño del más grande.
Desafortunadamente, Sakurako no conoce el valor de , por lo que tiene que calcular la respuesta para cada (1 \le k\le n).
La primera línea contiene un entero (1\le n\le 10^6) — cantidad de amigos de Sakurako.
La segunda línea contiene enteros a_1,\dots,a_n (-5\cdot 10^5\le a_i\le 5\cdot 10^5) — contribución de cada amigo.
Salida números. El -ésimo número denota el tamaño más grande del conjunto para k = i.
Ejemplo
En la primera prueba:
Cuando k=1, \mathcal{S}=\{1,2,3,4,6\};
Para k=2, se puede demostrar que el mayor posible es \mathcal{S}=\{1,3,4,6\};
Para k=3, k=4 y k=5, se puede demostrar que uno de los mayores posibles es \mathcal{S}=\{3,4,6\};
Para k=6, se puede demostrar que uno de los mayores posibles es \mathcal{S}=\{1,4\}.
( puntos): a_i=a_{i-1}+1 para todo 2\le i\le n;
( puntos): -10\le a_i\le 10;
( puntos): n\le 1000;
( puntos): -30\le a_i\le 30;
( puntos): sin restricciones adicionales.