Spēlētāju saraksta pārbaude

Galda tenisa turnīrā piedalās $2N$ spēlētāji, kas pēc reitinga sakārtoti pēc kārtas un sanumurēti sākot no visstiprākā (reitinga numurs (saīsināti - rn.) $1$) un beidzot ar visvājāko (rn. $2N$). Spēlētāju pāri tiek izlozēti, $N-1$ reizi atkārtojot šādas darbības:

• no līdz šim vēl nepaņemtajiem spēlētājiem tiek paņemts visstiprākais spēlētājs (ar vismazāko reitinga numuru) un
• no līdz šim vēl nepaņemtajiem spēlētājiem tiek izlozēts pretspēlētājs.

Atlikušie divi spēlētāji veido pēdējo spēlētāju pāri.

Piemēram, ja ir astoņi spēlētāji, tad pāru izloze var notikt šādi:

• 1. pāris: paņemts spēlētājs ar rn. $1$ un izvēlēts tā pretspēlētājs ar rn. $7$,
• 2. pāris: paņemts spēlētājs ar rn. $2$ un izvēlēts tā pretspēlētājs ar rn. $3$,
• 3. pāris: paņemts spēlētājs ar rn. $4$ un izvēlēts tā pretspēlētājs ar rn. $6$,
• 4. pāris: spēlētāji ar reitinga numuriem $5$ un $8$.

Izlozes organizētājs Konrāds ir ievērojis, ka, zinot šo algoritmu, pietiek pierakstīt izlozēto pretspēlētāju reitinga numurus, lai varētu atjaunot visu spēlētāju pāru sarakstu.

Diemžēl šajā pretspēlētāju reitinga numuru virknē var būt kļūdas. Nepieciešams noteikt, kāds mazākais pretspēlētāju reitinga numuru skaits šajā sarakstā jāaizstāj ar citiem, lai šo virkni būtu iespējams iegūt ar doto algoritmu. Jānosaka arī, kāds būs spēlētāju pāru saraksts pēc sākotnējās reitinga numuru virknes salabošanas.

Uzrakstiet datorprogrammu, kas dotai $N$ vērtībai un izlozētajiem pretspēlētāju reitingu numuriem, izvada mazāko nepieciešamo izmaiņu skaitu un visus spēlētāju pāru reitinga numurus, kas iegūti pēc aprakstītā algoritma, izmantojot salaboto sarakstu!

Pirmajā rindā dots naturāls skaitlis - spēlētāju pāru skaits $N$ ($N \leq 10^6$).

Nākamajās $N-1$ rindās katrā dots naturāls skaitlis, kas nepārsniedz $2N$. Katram $i$ ievaddatu $i+1$-ajā rindā dots tā spēlētāja, kurš tika izvēlēts kā pretspēlētājs $i$-tajā pārī, reitinga numurs.

Izvaddatu pirmajā rindā jāizvada vesels nenegatīvs skaitlis $K$ ($0 \leq K < N$) - mazākais izmaināmo reitinga numuru skaits izlozēto pretspēlētāju sarakstā.

Nākamajās $N$ izvaddatu rindās jāizvada spēlētāju pāru numuri. Katram $i$ ($1\leq i\leq N$) izvaddatu $i+1$-ajā rindā jābūt diviem, ar tukšumzīmi atdalītiem, naturāliem skaitļiem - $i$-tā pāra spēlētāju reitinga numuriem augošā secībā. Pirmo $N-1$ pretspēlētāju reitingu numuru sarakstam no ievaddatos doto pretspēlētāju reitingu numuru saraksta jāatšķiras tieši $K$ pozīcijās.