ในการเลือกตั้ง ส.ส. ครั้งล่าสุด ผลปรากฏว่าไม่มีพรรคการเมืองใดที่มีจำนวน ส.ส. เกินครึ่ง ดังนั้น พรรคการเมืองแต่ละพรรคต่างก็พยายามที่จะไปจับขั้วกับพรรคการเมืองอื่น เพื่อจัดตั้งรัฐบาลผสมขึ้นมาให้ได้ หัวหน้าพรรคการเมืองแต่ละพรรคก็อยากจะทราบว่า พรรคการเมืองของตนจะต้องไปจับขั้วกับพรรคการเมืองอื่นอย่างน้อยกี่พรรค จึงจะทำให้จำนวน ส.ส. ทั้งหมดของพรรคการเมืองของตนและของทุกพรรคที่ไปจับขั้วด้วย รวมกันแล้วมากกว่าครึ่งหนึ่งของจำนวน ส.ส. ทั้งหมดในสภา

งานของคุณ
จงเขียนโปรแกรมเพื่อรับจำนวน ส.ส. ของพรรคการเมืองต่างๆ และคำนวณว่าพรรคการเมืองแต่ละพรรคจะต้องไปจับขั้วกับพรรคการเมืองอื่นอย่างน้อยกี่พรรค จึงจะสามารถครองเสียงข้างมากในสภาได้

ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม N (3 ≤ N ≤ 300,000) แทนจำนวนพรรคการเมืองทั้งหมด

อีก N บรรทัดต่อมา ในบรรทัดที่ i+1 (1 ≤ i ≤ N) จะระบุจำนวนเต็ม Mi (1 ≤ Mi ≤ 1,000,000) แทนจำนวน ส.ส. ของพรรคการเมืองที่ i

รับประกันว่าจะไม่มีพรรคการเมืองใดที่มีจำนวน ส.ส. มากกว่าครึ่งหนึ่งของจำนวน ส.ส. ทั้งหมดในสภา และจำนวน ส.ส. ทั้งหมดจะมีไม่เกิน 2,000,000,000 คน

ข้อมูลส่งออก
มีทั้งหมด N บรรทัด โดยในบรรทัดที่ i (1 ≤ i ≤ N) แสดงจำนวนพรรคการเมืองน้อยที่สุดที่พรรคการเมืองที่ i ต้องไปจับขั้วด้วยเพื่อให้สามารถครองเสียงข้างมากในสภา

การให้คะแนน
30% ของข้อมูลทดสอบ จะมี N ≤ 5,000

ที่มา
การแข่งขัน IOI Thailand League เดือนมิถุนายน 2553
โจทย์โดย: สุธี เรืองวิเศษ
ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก

5 1
7 1
1 1
1 1
2 1
3
7 3
5 3
5 2
6 2
7 3
5 3
5 2
8
ที่มา http://programming.in.th/task/rev2_problem.php?pid=1119