Ергежейлі Франек әрқашан ойындардың барлық түрін жақсы көретін. Бір күні ол шатырда әкесінің заттарын ақтарып жүріп, Тетрис (Tetris) ойынына ұқсайтын бірдеңесі бар ескі ойын приставкасын тауып алды. Ол таныс ойынға ұқсағанымен, оның кейбір ережелері өзгеше болды.
Ойын бастапқыда бос, ені $10$ және биіктігі шексіз тақтада ойналады. Фигуралар жоғарыдан бірінен соң бірі, кіріс деректерінде берілген дәл сол ретпен құлайды.
Фигуралардың тек екі түрі бар:
I-фигурасы, биіктігі $4$ және ені $1$ тік жолақ тәрізді.O-фигурасы, биіктігі $2$ және ені $2$ тұтас шаршы тәрізді.
Фигура пайда болған кезде, Франек оны қайда тастайтынын таңдауы керек:
I-фигурасын $10$ бағанның кез келгеніне тастауға болады.O-фигурасын оның екі бағаны да тақта ішіне толығымен сыятындай етіп тастауға болады (яғни, $1$-ден $9$-ға дейінгі кез келген бағаннан бастап).
Фигура құлай бастағанда, ол бұрыннан бар блоктардың үстіне немесе тақтаның түбіне қонғанша тігінен төмен түседі. Фигураларды бұруға, ауада жан-жаққа жылжытуға немесе бөліктерге бөлуге болмайды. Фигура қонғаннан кейін, ол жабатын барлық ұяшықтар толады.
Тақтаның көлденең қатары блоктармен толық толтырылған сайын (яғни, сол биіктіктегі барлық $10$ бағанда блок болса), ол қатар жойылады. Оның үстіндегі барлық блоктар бір бірлікке төмен жылжиды. Егер бір уақытта бірнеше қатар толтырылса, олардың барлығы бірге жойылады.
Дәл төрт қатар бір мезгілде жойылған сайын сіз бір тетрис (tetris) ұпайын аласыз. Ойынның мақсаты — мүмкіндігінше көп тетрис жинау.
Бірінші тақтада фигуралар орналасуының үлгісі көрсетілген. $8$-ші бағанға I-фигурасын тастағаннан кейін, ол екінші және үшінші тақталарда көрсетілгендей құлай бастайды. Содан кейін төменгі төрт қатар жойылып, бір тетрис ұпайы беріледі де, төртінші тақта пайда болады.
Бәсекеقабілетті кішкентай ергежейлі болғандықтан, Франек максималды ұпай жинағысы келеді! Алайда ол ойынды жеткілікті деңгейде жақсы ойнай алмайды, сондықтан сіз оған көмектесуіңіз керек. Фигуралардың ретін алдын ала біле отырып, Франекке тиімді ойнаған жағдайда жинай алатын тетристердің максималды санын анықтауға көмектесіңіз. Сонымен қатар, осы ұпайға қол жеткізетін жүрістер тізбегін көрсетіңіз.
Кіріс деректері
Бірінші жолда фигуралар санын білдіретін бір бүтін сан $N$ берілген. Екінші жолда біріншіден соңғыға дейінгі фигуралар тізбегін сипаттайтын, тек I және O таңбаларынан тұратын ұзындығы $N$ жол берілген.
Шығыс деректері
Бірінші жолда Франек жинай алатын тетристердің максималды саны болып табылатын бір бүтін санды шығарыңыз. Екінші жолда $N$ бүтін саннан тұратын $c_1, c_2, \dots, c_N$ тізбегін шығарыңыз, мұндағы $c_i$ — $i$-ші фигура тасталуы тиіс баған нөмірі ($1$-ден бастап нөмірленеді). I-фигурасы үшін $c_i$ мәні $1 \le c_i \le 10$ шартын қанағаттандыруы керек. O-фигурасы үшін $c_i$ оның сол жақ бағанын білдіреді және $1 \le c_i \le 9$ шартын қанағаттандыруы керек.
Егер бірнеше тиімді тізбек болса, олардың кез келгенін шығаруға болады.
Шектеулер
$1 \le N \le 200\,000$.
Мысалдар
Кіріс 1
10 IIOIOIOOII
Шығыс 1
1 1 2 3 5 3 6 7 7 9 10
Ескертпе
Көрсетілген шығыс — жүрістердің жарамды тізбектерінің бірі ғана; басқа тізбектер де дәл сондай максималды тетрис санына қол жеткізуі мүмкін.