Sakurako və Qərib Permutasiya#409

Sakurako və Qərib Permutasiya

1 saniyə
256 meqabayt
Medium

Son zamanlar, Sakurako bir permutasiyası tapıb.

O, bu permutasiyanın bütün xüsusiyyətlərini başa düşmək üçün, onu daha yaxşı araşdırmaq istəyir.

Bunu etmək üçün, onu maraqlı bir xüsusiyyətə malik permutasiya p_1p_2\dots p_k şəklində ifadə etməlidir:

Həmçinin, əlavə bir xüsusiyyət olaraq: t[p_k[p_{k-1}[\dots[p_1[i]]\dots]]]=i.

Sizin tapşırığınız (k\le n-1) seçmək və p_1p_2\dots p_k permutasiyaları tapmaqdır. Əgər bir neçə cavab varsa, istənilənini çıxışa verə bilərsiniz.

a_1, a_2, \dots, a_n tam ədədlər ardıcıllığında əgər -dən -ə qədər hər bir tam ədədə dəqiq bir dəfə rast gəlinirsə o, permutasiya adlanır. Məsələn, [1, 5, 3, 4, 2] permutasiyadır. Lakin, [1, 3, 4] permutasiya deyil (burada -yə rast gəlinmir və -ə rast gəlinir, hansı ki, rast gəlinməməlidir) və [1, 2, 2, 3] də permutasiya deyil (burada -yə iki dəfə rast gəlinir və -ə rast gəlinmir).

Input

Birinci sətirdə bir tam ədəd (2\le n\le 5 \cdot 10^5) — permutasiyasının uzunluğu verilir.

İkinci sətirdə sayda tam ədəd t_1, t_2, , t_n (1\le t_i \le n) — permutasiya verilir. -nin permutasiya olduğuna zəmanət verilir. Həmçinin, permutasiyasının ən az indeksi üçün t[x]\neq x (1\le x\le n) olduğuna zəmanət verilir.

Output

Siz bir tam ədəd (1 \leq k\le n-1) çıxarmalısınız. Qeyd edək ki, -nı minimallaşdırmağa ehtiyac yoxdur.

Bundan sonra, seçdiyiniz permutasiyaları p_1, p_2, \dots, p_k çıxarmalısınız.

Çıxış çox böyük ola biləcəyindən, permutasiyaları tam çıxarmayacaqsınız. Bunun əvəzinə, hər permutasiya p_i üçün, p_{i}[q]\neq q olan bütün indekslərini çıxarmalısınız.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Scoring

  • ( bal): n\le 8;

  • ( bal): n\le 100;

  • ( bal): n \le 10^5;

  • ( bal): əlavə məhdudiyyətlər olmadan.