D. Мухлагийн бодлого

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Өчигдар супермаркетын хүнсний хэсэгт нь үзэсгэлэн худалдаа болсон юм. Үзэсгэлэн худалдаан дээр $n$ шилтэй халуун ногоо байсан. Үйл явдал болохоос өмнө шилнүүдийг зүүнээс баруун тийш $1$-с $n$ хүртэл дугаарласан. Үйл явдлын дараа шилнүүд холилдсон ба худалдагч тэдгээрийг дугаарынх нь өсөх дарааллаар эрэмбэлэхээр болсон.

Худалдагчид түүний мэдлийн онцгой машин байдаг. Машин 5 буюу түүнээс бага шил авч тэдгээрийг худалдагчийн хүссэнээр өөрчлөн эмхэлж чаддаг байна. Шилнүүдийг дарааллуулсан байх албагүйг анхаараарай. Жишээлбэл: $2$, $6$, $5$, $4$, $3$, $1$ сэлгэмэлээс $1$, $2$, $3$, $4$, $5$, $6$ сэлгэмэлийг авч чадна, хэрвээ шилнүүдээс хассан бол $1$, $2$, $3$, $5$ ба $6$ болно.

Бүх шилнүүдийг дугаарынх нь өсөх дарааллаар байрлуулахад хамгийн багадаа хэдэн үйлдэл хийх хэрэгтэй вэ?

Оролт

Эхний мөр нь $n$ ($1 ≤ n ≤ 10^{5}$) бүхэл тоог агуулна. Хоёр дахь мөр нь $n$ ширхэг зайгаар тусгаарлагдсан бүхэл $a_{i}$ ($1 ≤ a_{i} ≤ n$) тооуудыг агуулна. $i$-р тоо нь $i$-р байрлал дахь шилийг илэрхийлнэ. Бүх тоонууд нь заавал ялгаатай байна.

Гаралт

Эхний мөрөнд бүх шилнүүдийг дугаарынх нь өсөх дарааллаар байрлуулахад шаардлагатай хамгийн бага үйлдлийн тоог хэвлэнэ. Дараа нь бүх үйлдлүүдийн тодорхойлолтыг дараах хэлбэрээр хэвлэнэ.

Нэг үйлдлийн тодорхойлолтын эхний мөр авах хэрэгтэй шилнүүдийн тоо ($k$)-г заана, хоёр дахь мөр нь авах хэрэгтэй шилнүүдийн байрлалуудыг ($b_{1}, b_{2}, ..., b_{k}$) заана, гурав дахь мөр нь шилнүүдийн шинэ дарааллыг ($c_{1}, c_{2}, ..., c_{k}$) илтгэнэ. Үйлдэл биелэгдсэний дараа шил $b_{i}$ байрлалаас $c_{i}$ байрлалд очсон байна. ($b_{1}, b_{2}, ..., b_{k}$) олонлогийг өөрчилж тавиад ($c_{1}, c_{2}, ..., c_{k}$) олонлог болсон байх ёстой.

Хэрвээ олон шийдэл байгаа бол аль нэгийг гаргана.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
6
3 5 6 1 2 4
Гаралт
2
4
1 3 6 4 
3 6 4 1 
2
2 5 
5 2 
Оролт
14
9 13 11 3 10 7 12 14 1 5 4 6 8 2
Гаралт
3
4
2 13 8 14 
13 8 14 2 
5
6 7 12 5 10 
7 12 6 10 5 
5
3 11 4 1 9 
11 4 3 9 1 

Тэмдэглэл

Эхний жишээг авч үзье. Шилнүүдийг хоёр үйлдлээр эрэмбэлж болно.

Эхний үйлдлийн үед бид $1$, $3$, $6$, $4$ байрлал дахь шилнүүдийг аваад $1$ байрлалд $3$ байрлал дахь шилийг тавиад үйлдэд дуусна. Дараа нь $3$ байрлалд $6$ байрлал дахь шилийг тавиад, $6$ байрлалд $4$ байрлал дахь шилийг тавиад, мөн $4$ байрлалд $1$ байрлал дахь шилийг тавина.

Эхний үйлдэл дууссаны дараа дараалал иймэрхүү харагдах болно: $1$, $5$, $3$, $4$, $2$, $6$.

Хоёр дахь үйлдэлд $2$ ба $5$ байрлалыг сонгоод тэдний байрыг солино.

Сэтгэгдлүүдийг ачааллаж байна...