Jedan stari gusarski kapetan je na napuštenom otoku pronašao jako dug lanac. Lanac je jako star i godinama je izložen vanjskim uvjetima, pa sve karike nisu jednake čvrstoće. S obzirom da starom kapetanu ne treba toliko dug lanac, odlučio ga je razdvojiti na dva dijela. Jedan dio će koristit za sidro, a drugi će spremiti u brodsko skladište za kasnije potrebe. Kapetan razdvaja lanac na način da odstrani jednu kariku i na taj način dobije dva dijela lanca, odnosno dva nova lanca. Karika koju će izdvojiti ne smije se nalaziti na kraju lanca. Kapetanovo iskusno oko može točno odrediti čvrstoću svake pojedine karike. Međutim, ne zna odrediti ukupnu čvrstoću lanca, jer nije bio na nastavi kada se to učilo u višoj gusarskoj školi koju je pohađao. Ukupna čvrstoća lanca računa se kao zbroj čvrstoća svih karika u lancu. Iako se često kaže da je lanac čvrst koliko i njegova najslabija karika, naš kapetan iz iskustva zna da to nije istina. Kapetan želi odstraniti jednu kariku, tako da apsolutna razlika ukupnih čvrstoća novih lanaca bude minimalna. Odstranjenu kariku će baciti u more, pa ta karika neće biti dio ni jednog od novih lanaca. Kapetana zanima kolika je najmanja moguća apsolutna razlika u čvrstoći dvaju novih lanaca.

Ulaz U prvom redu se nalazi prirodan broj N (3 ≤ N ≤ 200 000), koji predstavlja broj karika u pronađenom lancu. NAPOMENA: U 70% test primjera duljina lanca neće biti veća od 1000 karika. U svakom od sljedećih N redaka nalazi po jedan prirodan broj ki (1 ≤ ki ≤ 1000), koji označava čvrstoću i-te karike.

Izlaz U prvom i jedinom retku potrebno je ispisati jedan cijeli broj, koji označava najmanju moguću apsolutnu razliku čvrstoća dvaju novih lanaca.