Сейчас у Дмитрия сессия, и он должен сдать \(n\) экзаменов. Сессия начинается в день \(1\) и длится \(d\) дней. \(i\)-й экзамен пройдёт в день \(a_i\) (\(1 \le a_i \le d\)), все \(a_i\) — различны.
Пример, где \(n=3\), \(d=12\), \(a=[3,5,9]\). Оранжевым — дни сдачи экзамена. Перед первым экзаменом Дмитрий отдохнёт \(2\) дня, перед вторым он отдохнёт \(1\) день и перед третьим он отдохнёт \(3\) дня. Для расписания сессии Дмитрий считает специальную величину \(\mu\) — наименьшее из времен отдыха перед экзаменом по всем экзаменам. Например, для картинки выше \(\mu=1\). Иными словами, для расписания он подсчитывает ровно \(n\) чисел — сколько дней он отдыхает между экзаменом сдачей экзамена \(i-1\) и \(i\) (для \(i=0\) между началом сессии и сдачей экзамена \(i\)). Затем он находит \(\mu\) — минимум среди этих \(n\) чисел.
Дмитрий считает, что может улучшить предложенное расписание сессии. Он может попросить изменить дату одного экзамена (изменить одно произвольное значение \(a_i\)). Помогите ему поменять дату так, чтобы все \(a_i\) остались различны, а значение \(\mu\) было как можно больше.
Например, для рассмотренного выше расписания Дмитрию наиболее выгодно перенести второй экзамен на самый конец сессии. Новое расписание примет вид:
Теперь длительности отдыхов перед экзаменами равны \([2,2,5]\). Следовательно, \(\mu=2\). Дмитрий может оставить предложенное расписание без изменений (если не существует способа передвинуть один экзамен так, что это приведёт к улучшению ситуации).
Выходные данные
Для каждого набора входных данных выведите максимальное возможное значение \(\mu\), если Дмитрий может перенести один любой экзамен на произвольный день. Все значения \(a_i\) должны остаться различны.
Примечание
Первый пример разобран в условии.
Одно из оптимальных изменений расписаний для второго примера:
Изначальное расписание.
Новое расписание
В третьем примере необходимо передвинуть экзамен с дня \(1\) на любой день от \(4\) до \(100\).
В четвёртом примере любое изменение расписания только уменьшит \(\mu\), соответственно расписание нужно оставить исходным.
В пятом примере необходимо перенести экзамен с дня \(1\) на любой день от \(100000000\) до \(300000000\).
Одно из оптимальных изменений расписаний для шестого примера:
Изначальное расписание.
Новое расписание
В седьмом примере каждый день занят экзаменами и перестроить расписание невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
3 12
3 5 9
2 5
1 5
2 100
1 2
5 15
3 6 9 12 15
3 1000000000
1 400000000 500000000
2 10
3 4
2 2
1 2
4 15
6 11 12 13
2 20
17 20
|
2
1
1
2
99999999
3
0
1
9
|