რიგი სასადილოსთან

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: USACO, 2007/08, FEB, BRONZE


ოლიმპიადის მონაწილე მოსწავლეები ძალიან ჭირვეულნი არიან სადილის დროს თანამეინახეთა არჩევისას. ისინი გაიყვნენ
ორ ჯგუფად (ჯგუფები შესაბამისად დანომრილია 1 და 2). თითოეულ ჯგუფს სურს ცალკე ისადილოს - ჯერ პირველ ჯგუფმა, 
ხოლო მერე - მეორემ. პრობლემა წარმოიშვა მაშინ, როდესაც მოსწავლეები სასადილოს წინ ერთ რიგად ჩამწკრივდნენ. ყოველ i-ურ მოსწავლეს აქვს პატარა ბარათი, ზედ დაწერილი D_i (1 ≤ D_i ≤ 2) რიცხვით, რომელიც აღნიშნავს თუ რომელ
ჯგუფს მიეკუთვნება მისი მფლობელი. ყველა N (1 ≤ N ≤ 30,000) მოსწავლე ერთ რიგად ჩამწკრივდა სასადილოს წინ, თუმცა
იოლი შესამჩნევია, რომ ისინი არ დაჯგუფდნენ თავიანთი ბარათების მიხედვით. მენეჯერმა გადაწყვიტა ასე მოიქცეს: ის მიემართება მოსწავლეთა მწკრივის გასწვრივ და ახდენს ბარათებზე რიცხვების ცვლილებას:
შლის ძველ რიცხვს და აწერს ახალს. ამგვარი ქმედებით ის ქმნის 112222 ან 111122 სახის მიმდევრობას, რათა ბარათთა ნომრები მწკრივში ზრდადობით იყოს დალაგებული. მენეჯერმა შეიძლება ზოგჯერ მოსწავლეთა მხოლოდ ერთ ჯგუფი შექმნას ხოლმე
(მაგალითად, 1111 ან 222). მენეჯერი ზარმაცია, ამიტომ მას აინტერესებს რა მინიმალური რაოდენობის ბარათებზე უნდა მოახდინოს ცვლილება, რათა ისინი
ზრდადობით დაალაგოს. მენეჯერს შეუძლია მხოლოდ ნომრის შეცვლა ბარათზე, ხოლო მოსწავლეთათვის ადგილების გაცვლა არ შეუძლია. შემავალი მონაცემების ფორმატი: * სტრიქონი 1: ერთი მთელი რიცხვი: N * სტრიქონები 2..N+1: (i+1)-ე სტრიქონი შეიცავს i-ური ძროხის ბარათის ნომერს - ერთი მთელი რიცხვი: D_i გამომავალი მონაცემების ფორმატი: * სტრიქონი 1: ერთი მთელი რიცხვი, რომელიც წარმოადგენს შესაცვლელი ბარათების მინიმალურ რაოდენობას მოსწავლეების ზემოთ აღწერილი წესით დასალაგებლად.

 




მაგალითები

შესატანი მონაცემები
7 2 1 1 1 2 2 1 დაკოპირება
გამოსატანი მონაცემები
2 დაკოპირება

შენიშვნა

იცვლება მხოლოდ პირველი და ბოლო ბარათები.