დროის ლიმიტი: 1 წმ
მეხსიერების ლიმიტი: 64 მეგაბაიტი
შემავალი მონაცემები: stdin
გამომავალი მონაცემები: stdout
წყარო: USACO, 2004/05, NOV, QUAL
ფერმერ ჯონი აკვირდება ძროხების ჯოგს, რათა დაადგინოს მათში რომელს აქვს საშუალო მონაცემები. მას აინტერესებს რომელი ძროხა იწველის რძის საშუალო მედიანურ რაოდენობას. ძროხები რომ დავალაგოთ მოწველილი რძის რაოდენობის მიხედვით, მაშინ მედიანური სიდიდის მქონე ძროხის ორივე მხარეს აღმოჩნდება სხვა სიდიდეების თანაბარი რაოდენობა.
მოცემულია ძროხების კენტი N (2 <= N <= 10,000) რაოდენობა, აგრეთვე რამდენ რძეს (1 ...1,000,000) იწველის თითოული მათგანი. მოძებნეთ მოწველილი რძის მოცულობებში მედიანური სიდიდე, ისე რომ მასზე ნაკლები ან ტოლი მოცულობები იყოს იმდენივე, რაც ამ მედიანურ სიდიდეზე მეტი ან ტოლი რძის მოცულობები.
შეტანის ფორმატი:
* სტრიქონი 1: მხოლოდ ერთი მთელი რიცხვი N
* სტრიქონები 2..N+1: ყოველი შეიცავს ერთ მთელ რიცხვს - რამდენ რძეს იწველის მომდევნო ძროხა.
გამოტანის ფორმატი:
* სტრიქონები 1: ერთი მთელი რიცხვი - რძის მოცულობის მედიანური სიდიდე.
შესატანი მონაცემები
5 2 4 1 3 5 დაკოპირება
გამოსატანი მონაცემები
3 დაკოპირება
მოცემულია 5 ძროხა მათი წველადობებით 1..5. სიდიდეები 1 და 2 ნაკლებია ან ტოლია 3-ზე , 4 და 5 კი 3-ის მეტია ან ტოლია.