CSES - Datatähti Open 2017 - Witch game
  • Time limit: 1.00 s
  • Memory limit: 512 MB
Consider a witch game with $n$ players: $3$ witches and $n-3$ villagers. The goal of the villagers is to find the witches.

Initially, each player knows their own role. In addition, each witch also knows the other witches, but the villagers have no additional information about the roles. The villagers should find the witches during the game.

A vote is organized, where each player accuses another player of being a witch. A witch never accuses a player who in fact is a witch. A villager may accuse either another villager or a witch.

You are given the results of the vote, and your task is to calculate the number of possible ways to select which players are the witches.


The first input line contains an integer $n$: the number of players. The players are numbered $1,2,\ldots,n$.

The next line contains $n$ integers $x_1,x_2,\ldots,x_n$. Here $x_k$ is the player that player $k$ accuses of being a witch.


You should print an integer: the number of ways to select which players are the witches.


2 5 4 1 4 5


Explanation: The witches can be $(1,3,5)$, $(1,3,6)$, $(2,3,6)$ or $(2,4,6)$.

Subtask 1 (23 points)
  • $3 \le n \le 100$
Subtask 2 (24 points)
  • $3 \le n \le 5000$
Subtask 3 (53 points)
  • $3 \le n \le 10^5$