Пожежогасильний робот#10033
Під час пожеж в Австралії, ділянка землі, де відбувається пожежа, представлена у вигляді прямої, поділеної на 10^9 частин, пронумерованих від до 10^9. Наразі пожежа охопила частин цієї ділянки. Для боротьби з вогнем був запрошений експерт з лісових пожеж, Мурад.
Мурад планує використати своїх пожежогасильних роботів. У нього є маленьких і великих роботів. Усі роботи працюють за однаковою системою. У системи є параметр — діапазон пожежі, який завжди є цілим числом. Якщо діапазон пожежі дорівнює , то маленький робот може загасити послідовних частин, починаючи з місця останньої зупинки, а великий робот — частин. Жоден робот не може переміщатися або змінювати своє місцезнаходження під час гасіння пожежі. Очевидно, що чим більший діапазон пожежі, тим більше електроенергії витрачають роботи. Тому Мурад прагне загасити пожежу з мінімально можливим діапазоном пожежі. Допоможіть Мураду визначити мінімально можливий діапазон пожежі, при якому можна загасити пожежу.
У першому рядку задано три числа: (1 \le n \le 2000), і (0 \le p, q \le 10^5, p + q > 0). У наступних рядках знаходиться по одному числу x_i (1 \le x_i \le 10^9) — координати палаючих частин ділянки.
Виведіть мінімально можливий діапазон пожежі, при якому можна загасити пожежу.
Приклад 1
Приклад 2