Jaś 和 Staś 正在玩 Bajtocką 战争游戏。一开始，每位玩家都会获得一叠 $n$ 张的牌。每张牌上写着一个数字。游戏以轮为单位进行。在每一轮中，每位玩家从自己牌堆的顶端抽出两张牌，并做出决定：弃掉其中一张，并将另一张交给对手（每一轮中必须弃掉一张，将另一张交给对手）。对手则会将收到的牌放入自己牌堆的底部。
当两位玩家的牌堆中都只剩下一张牌时，游戏结束。如果 Jaś 的最后一张牌上的数字是 $j$，Staś 的是 $s$，那么 Jaś 得到 $j-s$ 分，而 Staś 得到 $s-j$ 分。
我们假设玩家们都采取最优策略进行游戏（即按照上述规则最大化自己的得分）。Jaś 最多能得到多少分？
输入格式
输入的第一行包含一个整数 $n$（$1 \le n \le 1,000,000$），表示每位玩家收到的牌的数量。第二行包含一个长度为 $n$ 的整数序列 $a_{i}$（$1 \le a_{i} \le 1,000,000$），表示 Jaś 的牌堆，从牌堆顶端开始依次列出。第三行以同样的格式表示 Staś 的牌堆。
输出格式
你的程序应输出一个整数 —— 在双方都采取最优策略的前提下，Jaś 最终能获得的分数。
样例
输入
4 5 3 7 2 2 8 3 4
输出
1