Rinkimai

Pradinių duomenų failas:

rinkimai.in  

Rezultatų failas:

rinkimai.out  

Laiko apribojimas:

1 s.  

Atminties apribojimas:

32 Mb.  

Užduotis

Neseniai vyko Baitlandijos parlamento rinkimai. Dabar, kai rinkimų rezultatai jau paskelbti, partijos turi suburti koaliciją ir suformuoti vyriausybę.

Kiekviena partija gavo tam tikrą vietų skaičių parlamente. Koalicija turi būti toks partijų poaibis, kad visoms koalicijos partijoms bendrai priklausytų griežtai daugiau negu pusė visų parlamento vietų. Pageidautina, kad koalicija turėtų kuo daugiau vietų parlamente ir galėtų “prastumti” savo siūlomus nutarimus net jei keli koalicijos nariai nedalyvauja posėdyje.

Koalicija vadinama pertekline, jei iš jos galima pašalinti vieną partiją išlaikant daugumą (t. y. likusi koalicijos dalis vis vien turės daugiau nei pusę vietų parlamente). Be abejo, tokia partija neturės realios valdžios koalicijoje: likę koalicijos nariai galėtų priimti nutarimus neatsižvelgdami į ją.

Parašykite programą, kuri:

• perskaitytų rinkimų rezultatus iš pradinių duomenų failo,
• rastų neperteklinę koaliciją, turinčią didžiausią galimą vietų skaičių parlamente,
• išvestų koalicijos sudėtį į rezultatų failą.

Pradiniai duomenys

Pirmoje pradinių duomenų eilutėje įrašytas vienas sveikasis skaičius N (1 <= N <= 300) – rinkimuose dalyvavusių partijų skaičius. Partijos sunumeruotos nuo 1 iki N.

Antroje eilutėje įrašyta N tarpu atskirtų neneigiamų sveikųjų skaičių \(a_{1}\), …, \(a_{n}\), kur \(a_{i}\) rodo, kiek vietų parlamente gavo i-oji partija. Bendras vietų skaičius parlamente bus teigiamas ir neviršys 100000.

Rezultatai

Pirmoje rezultatų eilutėje turi būti įrašytas vienas sveikasis skaičius K – partijų skaičius neperteklinėje koalicijoje, turinčioje didžiausią galimą vietų skaičių.

Antroje eilutėje turi būti įrašyta K skirtingų sveikųjų tarpais atskirtų skaičių – tai koaliciją sudarančių partijų numeriai. Partijų numerių pateikimo tvarka nesvarbi.

Jei galimos kelios tokios koalicijos, pateikite bet kurią.

Pavyzdžiai

4
1 3 2 4

2
2 4