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.

Input

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.

Output

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

Example

Input:

6
2 5 4 1 4 5

Output:

4

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