Baseball Fans

First, find one representative fan for each team.

Consider querying the set of people from $1$ to $i$. If the return value increases compared to the previous prefix, then person $i$ supports a team that has not appeared before. We record person $i$ as a representative of that team.

After this process, we have exactly one representative for every team, and all representatives support different teams.

Now consider an unclassified person $p$. Take a subset $S$ of the representatives and query $S$ together with $p$. Since all representatives support distinct teams, the number of distinct teams among the representatives in $S$ is exactly $|S|$.

• If the return value is $|S|$, then $S$ contains the representative of $p$'s team.
• If the return value is $|S|+1$, then $S$ does not contain the representative of 's team.

Therefore, we can binary search over the representatives to determine which representative supports the same team as $p$.

Finding the representatives uses $N$ queries, and classifying each person uses $O(\log N)$ queries. Since $N \le 100$, the total number of queries is at most $1000$.