Побудова воріт

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

Зокрема, Фермер Джон починає рух із точки $(0,0)$ і робить $n$ кроків, щоразу переміщуючись на одну одиницю відстані на північ, південь, схід або захід. При кожному кроці він прокладає за собою відрізок паркану одиничної довжини. Наприклад, якщо його перший крок спрямований на північ, він встановлює відрізок паркану від $(0,0)$ до $(0,1)$. Фермер Джон може багаторазово повертатися в одні й ті самі точки і навіть кілька разів прокладати один і той самий відрізок паркану. Його паркан також може перетинати сам себе, якщо його шлях проходить через уже побудовану ділянку паркану.

Не дивно, що після завершення будівництва паркану Фермер Джон вельми незадоволений результатом. Зокрема, він помічає, що міг розділити деякі ділянки ферми на окремі області, так що тепер неможливо пройти з однієї області в іншу, не перетнувши паркан. Фермер Джон хоче виправити цю проблему, додавши ворота в паркан. Ворота можна встановити на будь-якому одиничному відрізку побудованого ним паркану, забезпечивши прохід між двома сторонами цього відрізка.

Визначте мінімальну кількість воріт, які Фермер Джон має встановити, щоб знову забезпечити можливість потрапити з будь-якої області ферми в будь-яку іншу.