삼각 분할

정$n$각형 $P$에 $P$의 두 꼭짓점을 잇고 서로 교차하지 않는 선분을 추가하면 $P$를 $n-2$개의 삼각형으로 분할할 수 있다. 예를 들어 정사각형은 두 개의 삼각형으로, 정오각형은 세 개의 삼각형으로, 정육각형은 네 개의 삼각형으로 분할할 수 있다. 이렇게 얻은 삼각형의 집합을 $P$의 삼각 분할이라 한다. $n$이 3보다 크면 $P$의 삼각 분할은 둘 이상 존재한다.

$P$의 삼각 분할 $T$가 정해지면, $T$의 두 삼각형 $a$와 $b$ 사이의 거리는 $a$에서 $b$로 이동할 때 인접한 두 삼각형의 경계를 넘는 횟수로 정의된다. 이때 이동하는 동안 항상 다각형 $P$의 내부에 있어야 하며, $P$의 경계를 넘어서 이동할 수는 없다.

예를 들어, 그림 J.1에 나타난 삼각 분할에서 $a$와 $d$의 거리는 3이다. $a$에서 $d$로 가려면 삼각형 $a$, $b$, $c$, $d$를 차례로 지나야 하고, 삼각형 사이의 경계를 세 번 넘어야 하기 때문이다.

그림 J.1 정육각형의 삼각 분할

삼각 분할 $T$의 지름은 $T$의 모든 삼각형 쌍 사이 거리의 최댓값이다. 정$n$각형 $P$의 삼각 분할 중 지름이 최소인 것을 찾고, 그 지름을 출력하는 프로그램을 작성하라.

입력은 표준 입력에서 받는다. 첫째 줄에 정$n$각형의 변의 개수 $n$이 주어진다. ($3 \le n \le 1\,000\,000$)

출력은 표준 출력에 한다. 정$n$각형의 삼각 분할 중 지름의 최솟값을 한 줄에 출력한다.