Partiya yığıncağı#11714
Sakurako-nun dostu var. Onlarin hər biri CodeCoders adlı riyazi proqramlaşdırma saytındakı töhfəsi ilə təsvir olunur. Dost bir ədəd a_i — onun töhfəsi ilə təsvir edilir.
Hazırda, bu dost arasında, dost dost ilə yalnız və yalnız |a_i-a_j| < k olduqda tanışdır. Sakurako mümkün qədər çox insanı 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çərsə, o zaman hər i, j \in \mathcal{S} üçün, i \neq j şərtilə |a_{x_i} - a_{x_j}| \ge k olmalıdır.
Bütün mümkün insan dəstələri arasından o, ən böyük dəstənin ölçüsünü bilmək istəyir.
Təəssüf ki, Sakurako -nın dəyərini bilmir, ona görə də hər üçün cavab tapmalıdır (1 \le k \le n).
Birinci sətirdə bir tam ədəd (1 \le n \le 10^6) — Sakurako-nun dostlarının sayı.
İkinci sətirdə 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.
ədəd çıxarın. -ci ədəd, k = i üçün dəstəsinin ən böyük ölçüsünü göstərir.
Nümunə
Birinci testdə:
k = 1 olduqda, \mathcal{S} = \{1, 2, 3, 4, 6\};
k = 2 üçün, ən böyük mümkün -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 -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 -lərdən biri \mathcal{S} = \{1, 4\} olduğu sübut edilə bilər.
(6 xal): a_i = a_{i-1} + 1 bütün 2 \le i \le n üçün;
(14 xal): -10 \le a_i \le 10;
(41 xal): n \le 1000;
(77 xal): -30 \le a_i \le 30;
(112 xal): əlavə məhdudiyyətlər olmadan.