Уже давно ученые наблюдают занятное поведение акул. Акулы, как и многие другие живые существа, в поисках пищи чередуют перемещения на маленькие отрезки внутри одной локации с переходами на более длительные расстояния между локациями.

Максу, начинающему биологу, досталась распечатка, содержащая перемещения акулы за каждый из $$$n$$$ последовательных дней в течение года. Длины всех передвижений оказались различными. По этим данным Макс решил посчитать, какое же количество локаций посетила морская хищница. Он предположил, что существует такое число $$$k$$$, что, если за один день акула переместилась на расстояние, строго меньшее $$$k$$$, то она не поменяла локацию; если же акула переместилась на расстояние, большее или равное $$$k$$$, то в этот день она перемещалась на новую локацию. При этом перемещение на новую локацию могло занять несколько дней, в каждый из которых акула переместилась на расстояние, не меньшее $$$k$$$.

Акула никогда не возвращается на старую локацию после того, как она ушла из нее. Таким образом, в последовательности из $$$n$$$ дней можно выделить отрезки, в течение которых акула перемещалась на расстояния, меньшие $$$k$$$: это соответствует одной локации. Аркадий хочет выбрать такое $$$k$$$, чтобы длины всех таких отрезков были одинаковы.

Найдите такое целое число $$$k$$$, что количество локаций в перемещениях акулы максимально возможно. Если существует несколько таких $$$k$$$, выведите минимальное.