농부 존은 N ( 1 <= N <= 1,000 ) 곳의 축사에 광 케이블을 설치하려고 한다. 그러나 축사는 연못 둘레 가장 자리 주변으로 원형으로 지어져 있다.
그래서 케이블은 인접한 축사사이로만 연결할 수 있다. 원형으로 연결되어 있다는 것은 N 번째 축사가 1 번째 축사와 인접 하고 있다는 것이다.
농부 존은 통신하고자하는 축사 사이만 통신이 가능하면 되므로 모든 축사를 연결할 필요는 없다. 더불어 가능하다면 케이블 수를 작게 하고자 한다. N 이 3 인 경우 1 - 2 - 3 으로 연결하거나 , 3 - 1 로 연결 가능하다.
입력의 예에서 축사 수가 5 이고 , 1 - 3 과 4 - 5 사이가 통신가능 하기 위해서 필요한 최소 케이블 수는 3 이다.
입력 5 2 1 3 4 5 출력 3
출처:USACO 2002 February