Ваша рабочая неделя состоит из \(n\) дней, пронумерованных от \(1\) до \(n\), после дня \(n\) снова идет день \(1\). И \(3\) из этих дней — выходные, одним из которых является последний день, день \(n\). Когда будут два остальных дня — вам предстоит выбрать.
Выбирая дни отдыха, вы преследуете две цели:
- Никакие два выходных дня не должны идти друг за другом. Обратите внимание, что вы не можете сделать день \(1\) выходным, потому что он следует за днем \(n\).
- Рабочие отрезки, оказавшиеся между выходными должны быть наименее похожи друг на друга. Более конкретно, если отрезки имеют длину \(l_1\), \(l_2\) и \(l_3\) дней, вы хотите максимизировать \(\min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|)\).
Выведите максимальное значение выражения \(\min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|)\), которое может быть получено.
Выходные данные
Для каждого набора входных данных выведите одно число — максимальное значение, которое может быть получено.
Примечание
На изображении ниже можно видеть решения из примера для первых двух наборов данных. Выбранные выходные изображены фиолетовым. Рабочие отрезки подчеркнуты зеленым.
В \(1\) наборе данных единственными вариантами для выходных являются дни \(2\), \(3\) и \(4\) (потому что дни \(1\) и \(5\) соседние с днем \(n\)). Поэтому единственная возможность расположить их, чтобы они не стали соседями — это выбрать дни \(2\) и \(4\). Таким образом \(l_1 = l_2 = l_3 = 1\), а ответ \(\min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|) = 0\).
Для \(2\) набора данных изображен один из способов выбора выходных. Рабочие отрезки имеют длины \(2\), \(1\) и \(4\) дней. Таким образом, минимальной разницей является \(1 = \min(1, 3, 2) = \min(|2 - 1|, |1 - 4|, |4 - 2|)\). Можно показать, что нет возможности сделать это число больше.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6
10
1033
|
0
1
342
|