Jaś gra ze Stasiem w Bajtocką Wojnę. Na początku rozgrywki każdy z graczy otrzymuje stos $ n $ kart. Na każdej z kart zapisana jest jedna liczba. Gra toczy się w turach. W czasie tury każdy gracz wyciąga dwie karty z wierzchu swojej talii i podejmuje decyzję, którą z nich odrzucić, a którą przekazać przeciwnikowi (w każdym ruchu jedną z kart należy odrzucić, a drugą przekazać przeciwnikowi). Przeciwnik wkłada otrzymaną kartę pod spód swojej talii.

Gra kończy się w momencie, gdy obaj gracze mają po jednej karcie. Jeśli liczba zapisana na karcie Jasia to $ j $, a liczba na karcie Stasia jest równa $ s $, to Jaś otrzymuje $ j-s $ punktów, a Staś $ s $ - $ j $ punktów.

Zakładamy, że gracze grają optymalnie (maksymalizują swój wynik liczony zgodnie z powyższą regułą). Ile punktów uda się zdobyć Jasiowi?

Input Format

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita $ n $ ($1 \le n \le 1\,000\,000$) oznaczająca liczbę kart, które otrzymali gracze. W drugim wierszu znajduje się ciąg $ n $ liczb całkowitych $ a_{i} $ ($1 \le a_{i} \le 1\,000\,000$), który opisuje kolejne karty w talii Jasia, począwszy od karty na wierzchu talii. Trzeci wiersz opisuje karty w talii Stasia, w analogicznym formacie.

Output Format

Twój program powinien wypisać na wyjście jedną liczbę całkowitą - liczbę punktów, które zdobędzie Jaś, przy założeniu optymalnej gry obu graczy.

Example

Input

4
5 3 7 2
2 8 3 4

Output

1