"Олонлог Эгзэ" сургуулийн сурагчид шинэ жилийн баяраар "монита" нэртэй нэгнийгээ нууцаар баярлуулах үйл ажиллагаа зохион байгуулж байна.

Сургууль нь N сурагчтай.

Сурагч бүр өөр нэг сурагчийг баярлуулахын тулд сугалаа сугалжээ.
Сугалаан дээр 1-ээс N хүртэлх тоонууд бичигдсэн бөгөөд эдгээрийг хольж тараасан байна.

Ингэснээр:

• 1-р сурагч a₁
• 2-р сурагч a₂
• ...
• N-р сурагч aₙ

дугаартай сурагчийг баярлуулахаар сугалсан байна.

Энд a₁, a₂, ..., aₙ нь 1..N тоонуудын сэлгэмэл (permutation) байна.

? Таны даалгавар

Сургуулийн нийгмийн ажилтан дараах 2 зүйлийг мэдэхийг хүсэж байна:

1️⃣ Алтан монита

Хоёр сурагч i, j (i ≠ j) нь:

a[i] = j ба a[j] = i

байвал тэднийг алтан монита хос гэнэ.

? Нэг хосыг зөвхөн 1 удаа тоолно.

2️⃣ Өөрийгөө сугалсан сурагч

Хэрэв: a[i] = i бол тухайн сурагч өөрийгөө сугалсан гэж үзнэ.

Оролт:

• Эхний мөрөнд нэг бүхэл тоо:

  • N — сурагчдын тоо

• Дараагийн мөрөнд N бүхэл тоо:

  • a₁, a₂, ..., aₙ

Гаралт:

• Эхний мөрөнд:

  • алтан монита хосын тоо

• Хоёрдугаар мөрөнд:

  • өөрийгөө сугалсан сурагчдын тоо

Хязгаарлалтууд:

• \(1 ≤ N ≤ 200000 \)
• 1 ≤ a[i] ≤ N a нь 1..N-ийн сэлгэмэл байна

Дэд бодлого

Жишээ:

Оролт-1

10 
1 2 4 8 7 9 5 3 6 10

Гаралт-1

2
3

Оролт-2

5
3 1 2 5 4

Гаралт-2

1
0