Konténer
Egy konténer raktárban N db konténer van egy sorban tárolva. A konténereket el akarják szállítani, ezért mindegyikre rá van írva, hogy melyik városba kell szállítani. A városokat 1-től 3-ig sorszámozzák. A konténereket át kell rendezni úgy, hogy balról jobbra először az 1-essel, majd a 2-essel, végül a 3-assal jelölt konténerek álljanak. A raktár majdnem tele van, csak az utolsó konténer után van egy konténer számára szabad hely. A rendezést a konténerek fölött mozgatható robottal végezhetjük, amely egy lépésben kiemel a helyéről egy konténert és átteszi azt a szabad helyre, ezzel az átmozgatott konténer helye lesz szabad.
Feladat
Írj programot, amely kiszámítja, hogy legkevesebb hány lépésben lehet rendezni a konténersort, majd megadja a rendezést! A rendezés végén a szabad helynek a sor végén kell lennie!
Bemenet
A KONTENER.BE állomány első sorában a konténerek N száma van
$(1\le {\tt N}\le 10000)$. A második sor N egész számot tartalmaz egy-egy szóközzel elválasztva. Az i-edik szám annak a városnak a sorszáma (1 és 3 közötti érték), ahova az i-edik konténert szállítani kell.
Kimenet
A KONTENER.KI állomány első sorába a rendezés végrehajtásához minimálisan szükséges lépések M számát kell írni! A következő M sor tartalmazza a sorrendben végrehajtandó mozgatásokat, soronként egy-egy mozgatást! Minden sorban két egész szám legyen egy szóközzel elválasztva; i és j, ami azt jelenti, hogy a lépés során az i-edik helyen lévő konténert a j-edik helyre kell átmozgatni! A kezdetben üres hely sorszáma N+1.
Példa
| KONTENER.BE | KONTENER.KI |
|
12 2 1 2 3 1 3 2 3 2 3 1 2 |
10 9 13 4 9 1 4 5 1 3 5 11 3 6 11 12 6 8 12 13 8 |