დროის ლიმიტი: 1 წმ
მეხსიერების ლიმიტი: 256 მეგაბაიტი
შემავალი მონაცემები: stdin
გამომავალი მონაცემები: stdout
წყარო: USACO, 2015/16, DEC, GOLD
ბესი და ელსი თამაშობენ მარტივ თამაშს, რომელშიც გამოიყენება 2N ცალი კარტი. კარტები გადანომრილია 1-დან 2*N-მდე და თანაბრადაა გაყოფილი მოთამაშეებს შორის: N ცალი კარტი ბესის და N ცალი კარტი ელსის. ისინი თამაშობენ Nრაუნდს და ყოველ რაუნდში ორივე მოთამაშე თითო კარტს ჩამოდის. პირველი N/2 რაუნდიდან თითოეულში ქულას იღებს ის მოთამაშე, რომელიც უფრო მაღალ კარტს ჩამოვა. ბოლო N/2 რაუნდში კი ქულას იღებს კი ქულას იღებს ის მოთამაშე, რომელიც უფრო დაბალ კარტს ჩამოვა.
ბესის შეუძლია წინასწარ განსაზღვროს, თუ რა თანმიმდევრობით ჩამოვა კარტებს ელსი. გამოთვალეთ ქულების რა მაქსიმალური რაოდენობა შეუძლია მოაგროვოს ბესიმ.
შესატანი მონაცემები: პირველ სტრიქონში შემოდის ერთი მთელი რიცხვი N (2≤N≤50,000, N ყოველთვის ლუწია).
მომდევნო N სტრიქონიდან თითოეული შეიცავს ელსის მიერ შესაბამის რაუნდში ჩამოსულ კარტს. მიაქციეთ ყურადღება, რომ ამ ინფორმაციით შესაძლებელია ბესის კარტების განსაზღვრაც.
გამოსატანი მონაცემები: ერთადერთ სტრიქონში გამოიტანეთ ბესის ქულათა მაქსიმალურად შესაძლო რაოდენობა.
შესატანი მონაცემები
4 1 8 4 3 დაკოპირება
გამოსატანი მონაცემები
2 დაკოპირება
შესატანი მონაცემები
4 1 8 4 3 დაკოპირება
გამოსატანი მონაცემები
2 დაკოპირება
ბესის კარტებია 2, 5, 6, და 7. მას შეუძლია მხოლოდ 2 ქულის მოგროვება: ერთის პირველ სვლაზე და მეორის '2' კარტით თამაშის მეორე ნახევარში.