ღამის მეფე და კენტობრიობა

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

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

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

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


ღამის მეფე დიდი ბრძოლისათვის ემზადება და ცდილობს დიდი არმია შეაგროვოს. ადამიანები კი კონკრეტული ტიპისები არიან:ყველა მათგანს რაღაც ნომერი აქვს მინიჭებული. თუ ეს ნომერი კენტია, მაშინ ღამის მეფე მოახერხებს საკუთარ არმიაში მათ შეყვანას, თუ ლუწია, მაშინ ვერ მოახერხებს. რადგანაც ღამის მეფეს სურს ძალიან დიდი არმია შეკრიბოს, უნდა ყველა ადამიანი საკუთარ ბნელ მხარეზე გადაიყვანოს. საკუთარი "Falx"-ის გამოყენებით, მას შეუძლია ერთი ტრანსფორმაციის გეკეთება: აირჩიოს კონკრეტული რიცხვი და ამ ტიპის ყველა ადამიანის ნომერი გაანახევროს.

მაგალითად, გვყავს ადამიანები: [2, 3, 6, 7, 6, 9, 6], თუ ღამის მეფე აირჩევს 6-ს და გაანახევრებს მას, შედეგად გვეყოლებიან შემდეგი ტიპის ადამიანები: [2, 3, 3, 7, 3, 9, 3]. 2-ის განახევრების შემდეგ კი ყველა რიცხვი კენტი გახდება [1, 3, 3, 7, 3, 9, 3]. აქედან გამომდინარე, სულ 2 ოპერაციაა საჭირო.

გრძელი ღამე ახლოვდება, შესაბამისად ღამის მეფეს სურს რაც შეიძლება ჩქარა, ანუ ნაკლები ოპერაციით ყველა ადამიანი გახადოს კენტი რიცხვის ტიპის.  (კონკრეტული ტიპის რიცხვის არჩევა და ყველა ამ ტიპის ადამიანის ნომრის განახევრება ერთი ოპერაციაა). დაეხმარეთ ღამის მეფეს არმიის გამთლიანებაში.

შესატანი მონაცემები: პირველი ხაზი შეიცავს ერთ რიცხვს nTests (1 <= nTests <= 10^4). დანარჩენი nTests ოდენობის ხაზითან თითოეული შეიცავს:     პირველ ხაზზე: n (1 <= n <= 10^5) ადამიანების საერთო რაოდენობას.  მეორე ხაზზე: მასივს, სადაც თითო ელემენტი არის ადამიანის ტიპი.

გამოსატანი მონაცემები: თითოეული ტესტისთვის დაბეჭდეთ ერთი რიცხვი: ოპერაციათა მინიმალური რაოდენობა.




მაგალითები

შესატანი მონაცემები
2 7 2 3 6 7 6 9 6 3 5 17 11 დაკოპირება
გამოსატანი მონაცემები
2 0 დაკოპირება

შენიშვნა

 

 

ამოცანის პირობა და ტესტები მოგვაწოდა გიგა ხიზანეიშვილმა.