Ідеальний маршрут

Обмеження: 2 сек., 256 МіБ

Планування ідеального маршруту для походу — справа нелегка. Для цього в Зеника є детальна карта українських Карпат. На карті позначено \(n\) гір. Координати \(i\)-тої гори \((x_i, y_i)\).

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

Не кожен маршрут є ідеальний. Для Зеника критерії ідеального маршруту такі:

• Усі сторони багатокутника паралельні осям координат, він не містить самоперетинів.

• Усі гори, що позначені на його карті лежать всередині чи на межі багатокутника.

• На маршруті немає двох послідовних поворотів ліворуч.

В Марічки вимоги дещо інші. Єдина її умова — щоб усі повороти на маршруті відбувалися саме на горах, які позначені на карті, а не десь серед лісу. Повороти поза відомими горами, Марічка називає жахливими поворотами.

На жаль, задовольнити вимоги обох мандрівників не завжди можливо. А тому Зеник хоче спланувати маршрут так, щоб він відповідав усім його критеріям та містив якнайменше жахливих поворотів.

Допоможіть Зенику з’ясувати яку найменшу кількість жахливих поворотів може містити маршрут.

Вхідні дані

У першому рядку задано одне ціло число \(n\) — кількість гір, позначених на карті Зеника.

У наступних \(n\) рядках задано по два цілих числа \(x_i\), \(y_i\) — координати гір. Усі координати гір різні.

Вихідні дані

У єдиному рядку виведіть одне ціле число — мінімальну кількість жахливих поворотів у маршруті що відповідає критеріям Зеника.

Обмеження

\(1 \le n\le 10^{5}\),

\(-10^{9} \le x_i, y_i \le 10^{9}\),

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 0 0 1 0 0 1	1

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 0 0 -1 0 1 0 0 -1 0 1	3

Примітки

Маршрут для першого прикладу:

Приклад маршруту з трьома жахливими поворотами для другого прикладу:

Приклад маршруту, який не задовольняє критерії Зеника, адже містить два послідовні повороти ліворуч, якщо рухатися по ньому в порядку обходу за годинниковою стрілкою: