Фермер Джон установил новую доильную машину. Она берёт так много энергии, что в амбаре часто выключается свет. Это случается так часто, что Беси запомнила карту амбара. Это позволяет ей быстрее находить путь к выходу в темноте. Теперь ей интересно узнать насколько дольше её путь в темноте.

Амбар описывается простым (несамопересекающимся) многоугольником с целочисленными вершинами (x1, y1) ... (xn, yn) перечисленными в порядке обхода по часовой стрелке. Его рёбра составляются чередующимися горизонтальными (параллельными оси Х) и вертикальными (параллельными оси Y) отрезками. Первое ребро может быть как горизонтальным, так и вертикальным. Выход расположен в точке (x1, y1). Беси начинает в некоторой вершине (xi, yi) для i > 1. Она идёт только по периметру амбара, по часовой стрелке или против часовой стрелки, потенциально изменяя направления движения, в любой вершине. Её цель - пройти минимальное расстояние и добраться до выхода. Это довольно просто, когда свет включён - просто выбрать между движением по часовой стрелке и движением против часовой стрелки.

Когда свет выключается, Беси в панике забывает вершину, в которой она находится. К счастью, она помнит точную карту амбара и поэтому она может вычислить свою позицию, двигаясь и опираясь на свои ощущения. Когда она находится в вершине, она может сказать это левый поворот или правый поворот, и является ли вершина выходом. Когда она идёт по ребру амбара, она может определить точную длину ребра после того, как пройдёт всё ребро. В общем сначала Беси двигается, чтобы определить, где она находится, а затем чтобы добраться к выходу за минимальное из оставшихся расстояний.

Помогите Беси определить минимальное количество, на которое возрастёт её путь в худшем случае при движении в темноте, по сравнению с движением при свете, полагая, что она движется оптимально в каждом случае. Оптимальная стратегия - такая, которая минимизирует увеличение расстояния в худшем случае.

Входные данные

Первая строка содержит n (4 ≤ n ≤ 200). Каждая из последующих n строк содержит по два целых числа, описывающих точки (xi, yi) в почасовом порядке обхода. Все целые числа -105 ... 105.

Выходные данные

Минимально возможное для худшего случая увеличение длины оптимального пути при походе в темноте по сравнению с походом при свете.

Пояснение

Одна оптимальная стратегия - двигаться по часовой стрелке - это оптимально, если начинать в вершинах 3 или 4 и добавляет 2 единицы расстояния, если она начнёт в вершине 2.