C. Васяа ба гоё массив

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Васяа-ийн төрсөн өдөр болох гэж байгаа ба түүний ээж түүнд $n$ урттай эерэг бүхэл $a$ массив өгөхөөр шийдсэн.

Васяа хамгийн их ерөнхий хуваагчтай массивийг гоё массив гэж бодсон. Түүний ээж мэдээж хэрэг түүнд аль болох гоё массив өгөхыг хүссэн. Харамсалтай нь дэлгүүрт зөвхөн $a$ массив л үлдсэн байсан. Худалдагч нь массивийн зарим элементийг бууруулж болно гэж хэлсэн ($k$-аас ихээр буруулж болохгүй).

Худалдагч $a$ матрицаас $b$ матрицийг олж авхад дараах дүрмийг дагаж авах боломжтой. Үүнд: $b_{i} > 0; 0 ≤ a_{i} - b_{i} ≤ k$; $1 ≤ i ≤ n$.

Васяа-аад өгөх гоё массивд хамгийн боломжтой массивийг олоход нь түүний ээжид туслаарай.

Оролт

Эхнй мөрөнд хоёр бүхэл $n$ ба $k$ $(1 ≤ n ≤ 3*10^{5}; 1 ≤ k ≤ 10^{6})$ тоонууд оруулна. Хоёр дахь мөрөнд $n$ ширхэг $a$ массивийн $a_{i}$ $(1 ≤ a_{i} ≤ 10^{6})$ элементүүдийг оруулна.

Гаралт

Ганц мөрөнд нэг тоо хэвлэнэ. Энэ тоо нь гоё массивийн хамгийн их ерөнхий хуваагч юм.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
6 1
3 6 10 12 13 16
Гаралт
3
Оролт
5 3
8 21 52 15 77
Гаралт
7

Тэмдэглэл

Эхний жишээнд бид энэ массивийг авч чадна:

$3 6 9 12 12 15$

Хоёр дахь жишээнд бид энэ дараагийн массивийг авна:

$7 21 49 14 77$

Сэтгэгдлүүдийг ачааллаж байна...