Matija i Damir nose različite predmete na tržnicu. Međutim, imaju vrlo različite pristupe svom poslu. Matija voli izazove i uvijek želi nositi što teže predmete kako bi pokazao svoju snagu. Damir, s druge strane, voli praktičnost i uvijek pokušava uzeti što lakše predmete kako bi se manje umorio. Danas su dobili zadatak prenijeti određeni broj predmeta s jedne strane tržnice na drugu. Kako bi bilo pošteno, odlučili su podijeliti predmete tako da svatko nosi točno polovicu. Naravno, obojica žele postići svoj cilj – Matija želi maksimalnu težinu, dok Damir želi minimalnu.

Dana vam je lista težina predmeta koje treba prenijeti. Svaki predmet ima težinu \(w_i\). Matija i Damir će podijeliti predmete tako da svatko nosi \(n/2\) predmeta (\(n\) je ukupan broj predmeta). Matija će uvijek birati najteže moguće predmete, dok će Damir birati najlakše. Vaš zadatak je odrediti maksimalnu razliku u težini tereta koji nosi Matija u odnosu na Damir.

Ulazni podatci

U prvome retku nalazi se prirodan broj \(n\) (\(2 \leq n \leq 10^5\)), ukupan broj predmeta, pri čemu je \(n\) uvijek paran broj. U drugome retku nalaze se \(n\) prirodnih brojeva od kojih \(i\)-ti \(w_i\) (\(1 \leq w_i \leq 10^6\)), predstavlja težinu \(i\)-tog predmeta.

Izlazni podatci

Ispišite traženi broj iz zadatka.

Podzadatci

Ulaz primjera 1

6
8 4 5 2 10 1

Izlaz primjera 1

16

Ulaz primjera 2

8
1 1 1 1 1 1 1 1

Izlaz primjera 2

0