1. Utrápený Marcel

Marcel má veľký sen. Jedného dňa by chcel byť skutočným vedcom v Slovenskej akadémii vied, tak ako jeho kamaráti Samko a Emko. Laboratórium vákuovej fyziky mu však zatiaľ dáva robiť iba podradné práce. Varí kolegom kávu, chodí po balíčky na poštu, seká uhorky, prípadne plní iné ich želania.

Jedného dňa ho Emko so Samkom poslali na nákup do Teska. Marcel si okrem nákupu kúpil aj dve veľké tašky, do ktorých chcel vkladať tovar. Kým predavač blokoval jeho nákup, Marcel rozmýšlal, ako tovar rozdeliť medzi tašky, aby ich hmotnosti boli čo najviac vyrovnané. Kedže v rade za ním je veľa ľudí, Marcel nechce zdržovať a ukladá tovar to tašiek jeden po druhom.

Po krátkom výpočte Marcel zistil, kedy má začať nákup ukladať do druhej tašky. Keď doniesol nákup svojim kolegom, spýtal sa ich, či aj oni vedia takúto úlohu vyriešiť. Pomôžte Samkovi a Emkovi vyriešiť tento problém.

Úloha

Marcel má dve tašky neobmedzenej veľkosti, do ktorých balí tovar v poradí, v akom mu ho predavač podáva. Postupuje pri tom tak, že niekoľko prvých predmetov vloží do prvej tašky a zvyšné predmety dá do druhej. Vašou úlohou je zistiť, koľko predmetov má dať do prvej tašky, aby bol rozdiel hmotností tašiek čo najmenší. Ak existuje viacero optimálnych riešení, potom vypíšte väčšie číslo (snažte sa teda dávať predmety do prvej tašky).

Formát vstupu

Na prvom riadku vstupu bude jedno kladné celé číslo \(n\) – počet predmetov v Marcelovom nákupe. Druhý riadok obsahuje postupnosť \(n\) kladných celých čísel oddelených medzerami – hmotnosti predmetov v poradí, v akom ich predavač podáva Marcelovi.

Pre jednotlivé testovacie sady platia nasledujúce obmedzenia:

Formát výstupu

Na výstup vypíšte jeden riadok obashujúci jedno číslo – počet predmetov, ktoré má Marcel dať do prvej tašky.

Príklad

Input:

5
7 3 2 8 1

Output:

2

V prvej taške bude \(7+3=10\) a v druhej \(2+8+1=11\).

Input:

6
2 4 7 1 2 3

Output:

3

Nezáleží na tom, či dáme do prvej tašky prvé dva, alebo prvé tri predmety, rozdiel hmotností tašiek bude rovnaký. V prípade rovnosti máme však pridať predmet do prvej tašky, preto je odpoveď \(3\).