题目描述

给定两个长为 $n$ 的由 $1 \sim n$ 构成的排列 $a, b$。你需要求出有多少个 $a$ 的 非空 连续子段是 $b$ 的子序列。

序列 $c$ 是序列 $a$ 的连续子段，当且仅当在序列 $a$ 的 开头和结尾 各删除若干（可能为 $0$）个元素，能够得到序列 $c$；序列 $c$ 是序列 $b$ 的子序列，当且仅当在序列 $b$ 中 任意位置 删除若干（可能为 $0$）个元素，能够得到序列 $c$。

输入格式

第一行输入 $1$ 个整数 $n$。

第二行输入 $n$ 个整数，表示排列 $a_1, \ldots, a_n$。

第三行输入 $n$ 个整数，表示排列 $b_1, \ldots, b_n$。

输出格式

第一行输出 $1$ 个整数，表示答案。

5
3 5 2 4 1 
2 4 5 3 1 

8

提示

数据范围

对于 $100\%$ 的数据，$1\le n\le 10^6$，$a,b$ 构成 $1 \sim n$ 的排列。

• 子任务 1（$10$ 分）：$n\le 5$。
• 子任务 2（$30$ 分）：$n\le 10^3$。
• 子任务 3（$30$ 分）：$a_i=i$。
• 子任务 4（$30$ 分）：无特殊限制。