Гасне світло (Золото)

Фермер Джон встановив новий доїльний апарат, але він споживає так багато енергії, що іноді в амбарі вимикається світло. Це трапляється настільки часто, що Бессі вивчила план амбару, щоб легше знаходити вихід у темряві.

Амбар має форму простого (без самоперетинів) прямокутника з вершинами в цілих координатах (x[1], y[1]) ... (x[n], y[n]), перерахованими за годинниковою стрілкою. Його ребра чергуються між горизонтальними (паралельними осі x) і вертикальними (паралельними осі y). Перше ребро може бути як вертикальним, так і горизонтальним. Вихід знаходиться в точці (x[1], y[1]). Бессі починає всередині амбару, в одній з вершин (x[i], y[i]) для i > 1. Вона може рухатися лише по периметру амбару, за годинниковою стрілкою або проти годинникової стрілки. Її мета — пройти мінімальну відстань до виходу. Це досить просто, коли світло увімкнено, оскільки вона може вибрати, який шлях коротший від поточного положення до виходу — за годинниковою стрілкою або проти годинникової стрілки.

Коли світло вимикається, Бессі панікує і забуває, в якій вершині вона знаходиться. На щастя, вона все ще пам'ятає точну карту амбару, тому може обчислити свою позицію, рухаючись по периметру і використовуючи свої відчуття. Коли вона стоїть у вершині (включаючи свою початкову вершину), вона може відчути внутрішній кут при цій вершині і також може визначити, чи є ця вершина виходом. Коли вона рухається вздовж амбару, вона може визначити точну довжину ребра, по якому пройшла. Бессі рухається за наступною стратегією: вона рухається за годинниковою стрілкою по периметру амбару, поки не відчує достатню кількість кутів і ребер, щоб визначити, в якій вершині вона зараз знаходиться. У цей момент вона легко може обчислити, як їй швидше дістатися до виходу — продовживши рух за годинниковою стрілкою або переключившись на рух проти годинникової стрілки.

Допоможіть Бессі визначити найбільшу величину, на яку зросте її шлях до виходу в темряві, порівняно з шляхом при світлі (розглянувши всі можливі положення стартової вершини).

Вхідні дані

Перший рядок містить n (4 ≤ n ≤ 200). Кожен з наступних n рядків містить два цілих числа, що описують точки (x[i], y[i]) в порядку обходу амбару за годинниковою стрілкою. Ці цілі числа в діапазоні від -10^5 до 10^5.

Вихідні дані

Виведіть найбільше число, на яке зросте відстань у найгіршій стартовій позиції.

Приклади

Примітка

У цьому прикладі Бессі спочатку може відчути, що вона стоїть на 90-градусному куті, але не може розрізнити вершини 2 3 4. Після кроку вперед по ребру в напрямку за годинниковою стрілкою Бессі або досягне виходу, або зможе однозначно визначити свою позицію, базуючись на довжині цього ребра. Вона отримає такі відстані:

Якщо вона стоїть у вершині 2: вона пройде 12 одиниць у темряві (1 одиницю до вершини 3, потім 11 одиниць до виходу). При світлі їй потрібно було б пройти відстань у 10 одиниць. Тому зайва відстань 2 для цієї вершини.

Якщо стартова вершина 3: вона пройде 11 одиниць в обох випадках.

Якщо стартова вершина 4: вона пройде 1 одиницю в обох випадках.

Найгірший випадок 12 - 10 = 2. Тому Бессі може гарантувати, що використовуючи свою стратегію, незалежно від стартової точки їй відстань у темряві перевищить відстань при світлі не більше ніж на 2.