题目描述

小 j 有个长度为 $n$ 的全排列 $a_1,a_2,…,a_n$，牢超也有个长度为 $n$ 的排列 $b_1,b_2,…,b_n$，他们开始玩一个游戏

每一轮回合的步骤是：

• 小 j 删除当前的第一个或最后一个，然后牢超删除当前的第一个或最后一个。

游戏持续到最后每个人都只剩下一个元素为止，小 j 剩下 $x$，牢超剩下 $y$。

如果 $x=y$ ，则牢超获胜；否则小 j 获胜，如果两个人都做到最优，最终谁会胜利？

一个长度为 $n$ 的全排列，$1$ 到 $n$ 只出现一次

输入格式

第一行正整数 $n$（$1 \le n \le 10^5$)。

第二行 $n$ 个整数 $a_i$（$1\le a_i\le n$)。

第三行 $n$ 个整数 $b_i$（$1\le b_i\le n$)。

保证 $a_i$ 互不相同，保证 $b_i$ 互不相同。

输出格式

如果牢超获胜输出 $1$，否则输出 $0$。

输入样例

3
1 2 3
2 3 1

输出样例

0

提示

样例中，小 j 先删掉 $3$，无论牢超删掉哪个，最后一定是小 j 胜利。