Partiya yığıncağı

Sakurako-nun $n$ dostu var. Hər biri onların CodeCoders adlı rəqabətli proqramlaşdırma veb-saytındakı töhfəsi ilə təsvir edilə bilər. Dost $i$ bir ədəd $a_i$ — onun töhfəsi ilə təsvir edilir.

Hazırda, bu $n$ dost arasında, dost $i$ dost $j$ ilə tanışdır, yalnız $|a_i-a_j|<k$ olduğu halda. Sakurako mümkün qədər çox insanı partiyaya dəvət etmək istəyir. Lakin, o, onların hamısının bir-biri ilə tanış olmamasını istəyir.

Rəsmi olaraq, əgər o, insanlardan ibarət bir dəstə $\mathcal{S}=\{x_1,x_2,\dots ,x_m\}$ dəvət etməyi seçsə, onda hər $i,j\in \mathcal{S}$ üçün $i\ne j$ şərti $|a_{x_i}-a_{x_j}|\ge k$ yerinə yetirilməlidir.

Mümkün olan bütün insan dəstələrindən, o, ən böyüyünün ölçüsünü bilmək istəyir.

Təəssüf ki, Sakurako $k$-nın dəyərini bilmir, buna görə də o, hər $k$ üçün cavabı hesablamaq məcburiyyətindədir $(1\le k\le n)$.

Giriş verilənləri

Birinci sətirdə bir tam ədəd $n$ ($1\le n\le 10^6$) — Sakurako-nun dostlarının sayı.

İkinci sətirdə $n$ tam ədəd $a_1,\dots ,a_n$ ($-5\cdot 10^5\le a_i\le 5\cdot 10^5$) — hər dostun töhfəsi.

Çıxış verilənləri

$n$ ədəd çıxarın. $i$-ci ədəd $k=i$ üçün $\mathcal{S}$ dəstəsinin ən böyük ölçüsünü göstərir.

Nümunələr

Qeyd

Birinci testdə:

• $k=1$ olduqda, $\mathcal{S}=\{1,2,3,4,6\}$;

• $k=2$ üçün, ən böyük mümkün $\mathcal{S}$-nin $\mathcal{S}=\{1,3,4,6\}$ olduğu sübut edilə bilər;

• $k=3$, $k=4$ və $k=5$ üçün, ən böyük mümkün $\mathcal{S}$-lərdən biri $\mathcal{S}=\{3,4,6\}$ olduğu sübut edilə bilər;

• $k=6$ üçün, ən böyük mümkün $\mathcal{S}$-lərdən biri $\mathcal{S}=\{1,4\}$ olduğu sübut edilə bilər.

Qiymətləndirmə

1. ($6$ xal): $a_i=a_{i-1}+1$ bütün $2\le i\le n$ üçün;

2. ($14$ xal): $-10\le a_i\le 10$;

3. ($41$ xal): $n\le 1000$;

4. ($77$ xal): $-30\le a_i\le 30$;

5. ($112$ xal): əlavə məhdudiyyətlər olmadan.