Розв’язок

Два числа мають однакову остачу від ділення на $d$ тоді й лише тоді, коли їхня різниця ділиться на $d$. Тому для фіксованої послідовності найбільше придатне $d$ дорівнює найбільшому спільному дільнику різниць сусідніх елементів. Різниці будь-яких інших пар також діляться на цей НСД, оскільки є сумами сусідніх різниць.

Позначимо a_i=x_{i+1}-x_i для 1 \le i < n. Побудуємо два масиви:

• p_i — НСД чисел a_1, a_2, \ldots, a_i, причому p_0=0;

• s_i — НСД чисел a_i, a_{i+1}, \ldots, a_{n-1}, причому s_n=0.

Розглянемо видалення елементів від $l$ до r=l+k-1. Різниці сусідніх елементів, що залишилися, складаються з трьох частин:

• різниці всередині лівої частини, їхній НСД дорівнює p_{l-2}, якщо l>1;

• різниці всередині правої частини, їхній НСД дорівнює s_{r+1}, якщо r<n;

• одна нова різниця x_{r+1}-x_{l-1}, якщо l>1 та r<n.

Відсутні частини не враховуємо. Для зручності обчислення НСД починаємо з нуля: НСД нуля та додатного числа дорівнює цьому числу.

Переберемо всі n-k+1 значень $l$. Для кожного знайдемо НСД наведених значень і виберемо найбільший результат. Нову різницю між частинами обчислюємо безпосередньо за двома елементами послідовності.

Доведення правильності

Для кожного видалення алгоритм враховує всі різниці сусідніх елементів нової послідовності: незмінені різниці зліва та справа, а також різницю між цими частинами, якщо вони обидві непорожні. Інших сусідніх пар після видалення немає.

НСД цих різниць ділить різницю будь-яких двох елементів, тому всі числа мають однакову остачу від ділення на нього. Водночас будь-яке придатне $d$ має ділити всі сусідні різниці, а отже, не може перевищувати їхнього НСД.

Таким чином, для кожного видалення алгоритм знаходить найбільше придатне $d$. Оскільки перебрано всі дозволені видалення, найбільший зі знайдених результатів є відповіддю.

Складність

Часова складність — O(n \log c), де c \le 2 \cdot 10^9 — найбільша можлива різниця двох вхідних чисел. Додаткова пам’ять — $O(n)$.