Уже давно ученые наблюдают занятное поведение акул. Акулы, как и многие другие живые существа, в поисках пищи чередуют перемещения на маленькие отрезки внутри одной локации с переходами на более длительные расстояния между локациями.
Максу, начинающему биологу, досталась распечатка, содержащая перемещения акулы за каждый из \(n\) последовательных дней в течение года. Длины всех передвижений оказались различными. По этим данным Макс решил посчитать, какое же количество локаций посетила морская хищница. Он предположил, что существует такое число \(k\), что, если за один день акула переместилась на расстояние, строго меньшее \(k\), то она не поменяла локацию; если же акула переместилась на расстояние, большее или равное \(k\), то в этот день она перемещалась на новую локацию. При этом перемещение на новую локацию могло занять несколько дней, в каждый из которых акула переместилась на расстояние, не меньшее \(k\).
Акула никогда не возвращается на старую локацию после того, как она ушла из нее. Таким образом, в последовательности из \(n\) дней можно выделить отрезки, в течение которых акула перемещалась на расстояния, меньшие \(k\): это соответствует одной локации. Аркадий хочет выбрать такое \(k\), чтобы длины всех таких отрезков были одинаковы.
Найдите такое целое число \(k\), что количество локаций в перемещениях акулы максимально возможно. Если существует несколько таких \(k\), выведите минимальное.
Примечание
В первом тестовом примере перемещения по локации являются перемещения в \(1\)-й и \(2\)-й дни (первая локация), в \(4\)-й и \(5\)-й (вторая локация), в \(7\)-й и \(8\)-й (третья локация). Таким образом, всего локаций три.
Во втором примере перемещений по локации является только перемещение во \(2\)-й день. Всего одна локация.