题目描述

ak机有两个长度长度为$n$的排列，并且想用计算机给他们存起来。

但ak机的计算机存储算法很神奇，它只会存储排列的子数组，并且不会存储重复的子数组。

他想知道，存储这两个排列需要多少次？

注：排列，指由1~$n$组成的长度为$n$的序列，且每个数字仅出现一次。

子数组：由原数组中若干个连续位置的数字构成

输入描述

第一行输入一个正整数$n(1\le n\le 10^5)$，代表排列的长度。

第二行输入$n$个正整数$a_i$，代表第一个排列。

第三行输入$n$个正整数$b_i$，代表第二个排列。

输出描述

输出一个整数，表示计算机存储的次数。

样例

输入

3
1 2 3
2 3 1

输出

8

样例解释

第一个排列的子排列有：$[1],[2],[3],[1,2],[2,3],[1,2,3]$

第二个排列的子排列有：$[2],[3],[1],[2,3],[3,1],[2,3,1]$

共有8个不同的子排列