მაღალი ბანქო, დაბალი ბანქო

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

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

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

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

წყარო: USACO, 2015/16, DEC, GOLD


ბესი და ელსი თამაშობენ მარტივ თამაშს, რომელშიც გამოიყენება 2N ცალი კარტი. კარტები გადანომრილია  1-დან 2*N-მდე და თანაბრადაა გაყოფილი მოთამაშეებს შორის: N ცალი კარტი ბესის და N ცალი კარტი ელსის. ისინი თამაშობენ Nრაუნდს და ყოველ რაუნდში ორივე მოთამაშე თითო კარტს ჩამოდის. პირველი N/2 რაუნდიდან თითოეულში ქულას იღებს ის მოთამაშე, რომელიც უფრო მაღალ კარტს ჩამოვა. ბოლო N/2 რაუნდში კი ქულას იღებს კი ქულას იღებს ის მოთამაშე, რომელიც უფრო დაბალ კარტს ჩამოვა.

ბესის შეუძლია წინასწარ განსაზღვროს, თუ რა თანმიმდევრობით ჩამოვა კარტებს ელსი. გამოთვალეთ ქულების რა მაქსიმალური რაოდენობა შეუძლია მოაგროვოს ბესიმ.

შესატანი მონაცემები: პირველ სტრიქონში შემოდის ერთი მთელი რიცხვი N (2N50,000, N ყოველთვის ლუწია).

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

გამოსატანი მონაცემები: ერთადერთ სტრიქონში გამოიტანეთ ბესის ქულათა მაქსიმალურად შესაძლო რაოდენობა.

 



მაგალითები

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

შენიშვნა

ბესის კარტებია 2, 5, 6, და 7. მას შეუძლია მხოლოდ 2 ქულის მოგროვება: ერთის პირველ სვლაზე და მეორის '2' კარტით თამაშის მეორე ნახევარში.