ყველაზე საშუალო

დროის ლიმიტი: 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-ის მეტია ან ტოლია.