P4089 [USACO17DEC] The Bovine Shuffle S
题目描述
Farmer John 坚信快乐的奶牛能产更多的奶,因此他在谷仓里安装了一个巨大的迪斯科球,并计划教他的奶牛跳舞!
在查阅了流行的奶牛舞蹈后,Farmer John 决定教他的奶牛“Bovine Shuffle”。Bovine Shuffle 包括他的 $N$ 头奶牛($1 \leq N \leq 100,000$)以某种顺序排成一行,然后进行连续的“洗牌”,每次洗牌可能会重新排列奶牛的顺序。为了让奶牛更容易找到自己的位置,Farmer John 为他的奶牛队伍标记了位置 $1 \ldots N$,因此队伍中的第一头奶牛位于位置 1,第二头位于位置 2,依此类推,直到位置 $N$。
一次洗牌由 $N$ 个数字 $a_1 \ldots a_N$ 描述,其中位于位置 $i$ 的奶牛在洗牌期间移动到位置 $a_i$(因此,每个 $a_i$ 都在 $1 \ldots N$ 范围内)。每头奶牛在洗牌期间都会移动到它的新位置。不幸的是,所有的 $a_i$ 不一定互不相同,因此多只奶牛可能会在洗牌期间尝试移动到同一位置,之后它们将在所有剩余的洗牌中一起移动。
Farmer John 注意到,无论进行多少次洗牌,他的队伍中某些位置始终会有奶牛。请帮助他计算这样的位置数量。
输入格式
输入的第一行包含 $N$,表示奶牛的数量。第二行包含 $N$ 个整数 $a_1 \ldots a_N$。
输出格式
请输出无论进行多少次洗牌,始终会有奶牛的位置数量。