题目描述

给定两个长为 $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

提示

【数据范围】

本题采用捆绑测试。

• Subtask #1（$10\ \text{pts}$）：$n\le 5$。
• Subtask #2（$30\ \text{pts}$）：$n\le 10^3$。
• Subtask #3（$30\ \text{pts}$）：$a_i=i$。
• Subtask #4（$30\ \text{pts}$）：无特殊限制。

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