题目描述

Alice 和 Bob 正在玩一个轮流取石子的游戏，Alice 先手。

总共有 n 个石子排成一排，每个石子都有一个特定的价值。但有趣的是，Alice 和 Bob 对每个石子的价值评判标准不同。双方都知道对方的价值标准。

给定两个长度为 n 的整数数组 a 和 b，其中 a[i] 表示 Alice 认为第 i 个石子的价值，b[i] 表示 Bob 认为第 i 个石子的价值。

游戏规则如下：

1. 玩家轮流进行，每次轮到自己时，必须从剩余石子中取出一个。
2. 取出第 i 个石子后，该玩家获得其对应的价值分数（Alice 取则加 a[i]，Bob 取则加 b[i]）。
3. 所有石子被取完后，游戏结束。得分较高的玩家获胜。如果得分相同，则为平局。
4. 两位玩家都会采用 最优策略 进行游戏。

输入格式

第一行，一个整数 n，表示石子的数量。

第二行，n 个整数，表示数组 a。

第三行，n 个整数，表示数组 b。

输出格式

输出一行一个整数：

• 如果 Alice 获胜，输出 1。
• 如果 Bob 获胜，输出 -1。
• 如果游戏平局，输出 0。

样例输入 1

2
1 3
2 1

样例输出 1

1

样例说明 1

• 如果 Alice 先取第二个石子（价值a[2]=3），她得到3分。
• 随后 Bob 只能取第一个石子（价值b[1]=2），得到2分。
• 最终 Alice 获胜。

样例输入 2

2
1 2
3 1

样例输出 2

0

样例说明 2

• Alice 取第一个石子（a[1]=1），得1分。
• Bob 取第二个石子（b[2]=1），得1分。
• 双方打平。

样例输入 3

3
2 4 3
1 6 7

样例输出 3

-1

样例说明 3

• 一种可能的进行方式是：Alice 取第二个石子（a[2]=4），Bob 取第三个石子（b[3]=7），Alice 再取第一个石子（a[1]=2）。最终 Alice 得 6 分，Bob 得 7 分，Bob 获胜。
• 可以证明，在此样例中无论 Alice 如何操作，Bob 总能获胜。

数据范围

• 对于 100% 的数据，1 <= n <= 10^5
• 1 <= a[i], b[i] <= 100