პრივილეგირებული ძროხები

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

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

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

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

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


 
იმის მიხედვით, თუ რამდენ რძეს იწველის, თითოეულ N (1 <= N <= 1,000)
ძროხათაგანს მინიჭებული აქვს პრივილეგიის ნომერი 1, 2, ან 3, რომელიც
განსაზღვრავს, თუ როდის უნდა დალიოს ძროხამ ჭიდან წყალი - სხვაზე ადრე,
თუ სხვაზე გვიან (ჯერ 1-იანები სვამენ, მერე 2-იანები და ბოლოს 3-იანები).
გულმავიწყ ძროხებს სულ ავიწყდებათ თავიანთი ნომრები, სანამ ფერმერი ჯონი
მათ არ შეახსენებს. ამის გამო ძროხები რიგში არეულად დგებიან და ფერმერი
ჯონი ყოველთვის იძულებულია გადაალაგოს ხოლმე ისინი ისეთი თანმიმდევრობით,
რომ თავში იდგნენ 1-იანები, შემდეგ 2-იანები და ბოლოს 3-იანები. ძროხები,
როგორც მოგეხსენებათ, ზარმაცები არიან და ცდილობენ, რომ გადალაგება
მინიმალური ცვლილებებით მოხდეს.

შეტანის ფორმატი:
* სტრიქონი 1: ერთი მთელი რიცხვი: N
* სტრიქონები 2..N+1: სტრიქონი i+1 შეიცავს ერთ მთელ რიცხვს, რომელიც წარმოადგენს პრივილეგიის ნომერს


გამოტანის ფორმატი:
* სტრიქონი 1: ერთი მთელი რიცხვი, რომელიც წარმოადგენს იმ მინიმალურ გადანაცვლებათა
რაოდენობას, რომელიც ძროხების გადალაგებისათვის არის აუცილებელი



მაგალითები

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

შენიშვნა

 

გამოტანის განმარტება:

აქ არის ერთი გზა:
2   2   2<  1   1
2<  1   1   1   1
1<  2   2   2   2
3   3<  2   2   2
3   3   3   3<  2
3   3   3   3   3
2   2<  3   3   3
3   3   3   3   3
1   1   1<  2<  3