E. Kitoblar aylanishi

Litseyning kitobxonlar klubida N ta o‘quvchi bor, ular 1 dan N gacha raqamlangan. Har bir o‘quvchining o‘z kitobi bor va dastlab hamma o‘z kitobini ushlab turibdi.

Klub qoidasi bo‘yicha har kuni kechqurun i-o‘quvchi qo‘lidagi kitobni pᵢ-o‘quvchiga beradi. p₁, p₂, …, pₙ — 1 dan N gacha sonlarning o‘rin almashtirishi: har kim kuniga aynan bitta kitob beradi va aynan bitta kitob oladi (pᵢ = i bo‘lsa, o‘quvchi kitobni o‘zida qoldiradi).

Klub rahbari ikki narsani bilmoqchi:

1. Necha kechadan keyin birinchi marta hamma o‘quvchi bir vaqtda yana o‘z kitobini ushlab turadi? Bu son juda katta bo‘lishi mumkin — uni 10⁹ + 7 ga bo‘lgandagi qoldig‘ini chiqaring.
2. Har bir o‘quvchi uchun: uning o‘z kitobi necha kechadan keyin birinchi marta unga qaytadi?

Kirish ma’lumotlari

Birinchi qatorda bitta butun son N — o‘quvchilar soni.

Ikkinchi qatorda N ta butun son p₁, p₂, …, pₙ.

Chiqish ma’lumotlari

Birinchi qatorda bitta butun son — hamma kitob birinchi marta bir vaqtda egasiga qaytadigan kechalar sonining 10⁹ + 7 ga bo‘lgandagi qoldig‘i.

Ikkinchi qatorda bo‘sh joy bilan ajratilgan N ta butun son: i-son — i-o‘quvchining kitobi unga birinchi marta qaytadigan kechalar soni.

Cheklovlar

• 1 ≤ N ≤ 2·10⁵
• 1 ≤ pᵢ ≤ N, barcha pᵢ har xil
• Kechalar soni kamida 1: hech narsa o‘zgarmasa ham, birinchi kecha o‘tishi kerak.

1-misol: 1-o‘quvchining kitobi 1 → 2 → 3 → 1 yo‘lni bosib, 3-kechada qaytadi; 2- va 3-o‘quvchining kitobi ham 3 kechada qaytadi. 4- va 5-o‘quvchi kitob almashib turadi — 2 kechada qaytadi. Hamma birdaniga 6-kechada qaytadi: 6 soni 3 ga ham, 2 ga ham bo‘linadi.

2-misol: hamma kitobni o‘zida qoldiradi — birinchi kechadan keyinoq hamma o‘z kitobini ushlab turibdi.