样例下载

题目描述

$N$ 个不超过 $N$ 的正整数从左向右排成一排，形成一个序列 $A$：$A_1, A_2, ……, A_N$。

另外 $N$ 个不超过 $N$ 的正整数从左向右也排成一排，形成一个序列 $B$：$B_1, B_2, ……, B_N$。

你可以进行如下操作一次且仅一次：选择序列 $A$ 的一个区间，将该区间内的数整体翻转顺序。序列 $B$ 不允许操作。

显然，你有 $(N+1)N/2$ 种操作方式，即你有 $(N+1)N/2$ 个不同区间可以选择。假设你使用第 $i$ $(1 ≤ i ≤ (N+1)N/2 )$ 种操作方式将所选区间翻转后，可以使得恰好有 $M_i$ 个不同的位置 $P_1, P_2, ……, P_{M_i}$ 满足 $A_{P_j} = B_{P_j}$ $(1 ≤ j ≤ M_i, 1 ≤ P_1 < P_2 < … <P_{M_i} ≤ N)$。

求 $\sum_{i=1}^{(N+1)N/2} M_i$。

输入格式

第一行：一个整数 $N$。

第二行：序列 $A$ 的 $N$ 个元素 $A_1, A_2, ……, A_N$。

第二行：序列 $B$ 的 $N$ 个元素 $B_1, B_2, ……, B_N$。

输出格式

一个整数，表示答案。

输入样例

3
1 2 3
3 2 1

输出样例

6

样例解释

样例中 N = 3

共有 N(N+1)/2 = 6 种操作方式

• （1）长度为 1 的区间有 3 个，翻转后 M_i = 1
• （2）长度为 2 的区间有 2 个，翻转后 M_i = 0
• （3）长度为 3 的区间有 1 个，翻转后 M_i = 3

故 $\sum M_i$ = 1+1+1+0+0+3 = 6

数据范围

100% 的数据：$1 ≤ N ≤ 5×10^5$, $1 ≤ A_i, B_i ≤ N$。其中：

• 10% 的数据：$N ≤ 100$。
• 10% 的数据：$N ≤ 5000$。
• 20% 的数据：$1 ≤ A_i, B_i ≤ N$ 且随机生成。
• 20% 的数据：$1 ≤ A_i, B_i ≤ 2$ 且随机生成。