Зная, что счастливые коровы дают больше молока, Фермер Джон установил гигантский диско-шар в амбаре и планирует научить танцевать своих коров.
ФД выбрал танец "Bovine Shuffle", в котором n коров выстроены в ряд в некотором порядке, затем они выполняют успешную перестановку, которая потенциально может переупорядочить коров. ФД пометил позиции коров 1 .. n, так, что первая корова в ряду стоит на позиции 1, вторая - на позиции 2, и т.д. до позиции n.
Перестановка описывается n числами a[1]
.. a[n]
, означающими, что корова с позиции i переместится в позицию a[i]
(все a[i]
в интервале 1 .. n). Каждая корова во время перестановки идёт на свою новую позицию. К несчастью, всеa a[i]
не обязательно различные, поэтому несколько коров могут во время перестановки придти в одну и ту же позицию. После чего они будут ходить вместе все оставшиеся перестановки.
ФД заметил, что некоторые позиции содержат коров, сколько перестановок ни сделай. Помогите ему посчитать количество таких позиций.
Первая строка содержит n (1 ≤ n ≤ 10^5
) - количество коров. Следующая строка содержит n целых чисел a[1]
.. a[n]
.
Выведите количество позиций, в которых всегда остнутся коровы, вне зависимости от количества выполненных перестановок.