1119 : รัฐบาลผสม (coalition)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)

ประเทศหนึ่งในแถบเอเชียตะวันออกเฉียงใต้ มีการปกครองในรูปแบบรัฐสภา โดย ส.ส. ในสภาจะเป็นผู้ลงคะแนนเลือกนายกรัฐมนตรี ซึ่งผู้ที่จะได้รับเลือกเป็นนายกรัฐมนตรีนั้นจะต้องได้รับเสียงสนับสนุนจาก ส.ส. มากกว่าครึ่งหนึ่งของจำนวน ส.ส. ทั้งหมดในสภา จากนั้นนายกรัฐมนตรีก็จะเป็นผู้จัดตั้งคณะรัฐมนตรีขึ้นมาทำหน้าที่บริหารประเทศต่อไป

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

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

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

ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม 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
7
1
1
2
3
1
1
1
1
1
7
5
5
6
7
5
5
8
3
3
2
2
3
3
2

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 19 ผู้เยี่ยมชมและ 0 สมาชิก (7 บอท)