题目描述

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_1, a_2, \dots, a_n$。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$。

输出格式

输出一行一个整数：

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

样例

2
1 3
2 1

1

样例解释

Alice 先取第二个石子（价值 $a_2=3$），得到 $3$ 分；随后 Bob 只能取第一个石子（价值 $b_1=2$），得到 $2$ 分；最终 Alice 获胜。

2
1 2
3 1

0

样例解释

Alice 取第一个石子（$a_1=1$），得 $1$ 分；Bob 取第二个石子（$b_2=1$），得 $1$ 分；双方打平。

3
2 4 3
1 6 7

-1

样例解释

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

数据范围

• $1 \le n \le 10^5$
• $1 \le a_i, b_i \le 100$