버섯 세기

버섯 전문가 Andrew는 싱가포르에 서식하는 버섯을 연구한다.

연구의 일환으로 Andrew는 $0$부터 $n-1$까지 번호가 붙은 버섯 $n$개를 채집했다. 각 버섯은 A와 B라 불리는 두 종 중 하나에 속한다.

Andrew는 버섯 $0$이 종 A에 속한다는 사실을 알고 있지만, 두 종이 겉보기에 같아서 버섯 $1$부터 $n-1$까지의 종은 알지 못한다.

다행히 Andrew의 실험실에는 이를 알아내는 데 도움이 되는 기계가 있다. 이 기계를 쓰려면 버섯 두 개 이상을 원하는 순서로 기계 안에 일렬로 넣고 전원을 켜야 한다. 그러면 기계는 서로 인접한 버섯 쌍 중 종이 다른 쌍의 개수를 계산한다. 예를 들어 종이 $[A,B,B,A]$인 버섯을 그 순서로 기계에 넣으면 결과는 $2$이다.

그러나 기계를 작동하는 비용이 매우 비싸기 때문에 기계는 제한된 횟수만 사용할 수 있다. 또한 기계를 사용하면서 넣은 버섯의 총 개수는 $100\;000$개를 넘을 수 없다. 이 기계를 사용해 Andrew가 채집한 종 A 버섯의 개수를 세도록 도와라.

• $2 \leq n \leq 20\;000$