Baseball Fans

먼저 각 팀의 대표 팬을 한 명씩 찾는다.

$1$번부터 $i$번까지의 사람들을 모두 포함하는 집합에 대해 query를 호출한다고 하자. 이 반환값이 이전보다 증가했다면, 방금 추가된 $i$번 사람은 지금까지 등장하지 않았던 새로운 팀의 팬이다. 따라서 $i$번 사람을 그 팀의 대표로 기록한다.

이 과정을 마치면 모든 팀에 대해 대표 팬을 정확히 한 명씩 확보할 수 있다. 대표 팬들은 모두 서로 다른 팀을 응원한다.

이제 아직 분류되지 않은 사람 $p$를 생각하자. 대표 팬들의 어떤 부분집합 $S$에 $p$를 함께 넣어 질의한다. 대표 팬들은 서로 팀이 다르므로, $|S|$명의 대표 팬만 고르면 서로 다른 팀의 수는 $|S|$이다.

• 반환값이 $|S|$라면, $S$ 안에 $p$와 같은 팀의 대표 팬이 있다.
• 반환값이 $|S|+1$이라면, $S$ 안에는 와 같은 팀의 대표 팬이 없다.

따라서 대표 팬들의 배열에서 이분 탐색을 수행하여, $p$가 어떤 대표 팬과 같은 팀인지 찾을 수 있다.

대표 팬을 찾는 데 $N$번의 질의를 사용하고, 각 사람을 분류하는 데 $O(\log N)$번의 질의를 사용한다. $N \le 100$이므로 전체 질의 수는 $1000$번 이하이다.