题目 | Moscow Gorillas

Codeforces Round 852 (Div. 2)

D. Moscow Gorillas

https://codeforces.com/problemset/problem/1793/D

2 seconds / 256 megabytes

standard input / standard output

Problem

In winter, the inhabitants of the Moscow Zoo are very bored, in particular, it concerns gorillas. You decided to entertain them and brought a permutation $p$ of length $n$ to the zoo.

A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in any order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ occurs twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$, but $4$ is present in the array).

The gorillas had their own permutation $q$ of length $n$. They suggested that you count the number of pairs of integers $l,r$ ($1\le l\le r\le n$) such that $\mathrm{MEX}([p_l,p_{l+1},\dots ,p_r])=\mathrm{MEX}([q_l,q_{l+1},\dots ,q_r])$.

The $\mathrm{MEX}$ of the sequence is the minimum integer positive number missing from this sequence. For example, $\mathrm{MEX}([1,3])=2$, $\mathrm{MEX}([5])=1$, $\mathrm{MEX}([3,1,2,6])=4$.

You do not want to risk your health, so you will not dare to refuse the gorillas.

Input

The first line contains a single integer $n$ ($1\le n\le 2\cdot {10}^5$) — the permutations length.

The second line contains $n$ integers $p_1,p_2,\dots ,p_n$ ($1\le p_i\le n$) — the elements of the permutation $p$.

The third line contains $n$ integers $q_1,q_2,\dots ,q_n$ ($1\le q_i\le n$) — the elements of the permutation $q$.

Output

Print a single integer — the number of suitable pairs $l$ and $r$.

Examples

Input

3
1 3 2
2 1 3

Output

2

Input

7
7 3 6 2 1 5 4
6 7 2 5 3 1 4

Output

16

Input

6
1 2 3 4 5 6
6 5 4 3 2 1

Output

11

Note

In the first example, two segments are correct – $[1,3]$ with $\mathrm{MEX}$ equal to $4$ in both arrays and $[3,3]$ with $\mathrm{MEX}$ equal to $1$ in both of arrays.

In the second example, for example, the segment $[1,4]$ is correct, and the segment $[6,7]$ isn't correct, because $\mathrm{MEX}(5,4)\ne \mathrm{MEX}(1,4)$.

题解

首先，我们从 $1$ 开始，维护完整包含了 $1\sim x$ 的区间的左右端点 $p_{min},p_{max}$ ($p_{min}\le p_{max}$). 维护方法也简单，如果要从 $x$ 向后递推到 $x+1$，则先找到 $p,q$ 序列里 $x+1$ 这个数在哪，记靠左的位置为 $mn$，靠右的位置为 $mx$ ($mn\le mx$)，然后更新：

• $p_{min}=min\{p_{min},mn\}$
• $p_{max}=min\{p_{max},mx\}$

我们找区间时，也是从 $\mathrm{MEX}$ 值为 $1$ 的开始向上找。如果我们现在已经计算出了 $\mathrm{MEX}$ 值为 $1\sim x$ 的数目，接下来我们找 $\mathrm{MEX}$ 值为 $x+1$ 的区间数目。

首先我们找到 $p,q$ 序列里 $x+1$ 这个数在哪，记为 $mn,mx$. 接下来，我们对 $mn,mx$ 与 $p_{min},p_{max}$ 的位置进行分类讨论：

• 情况一：$p_{max}<mn$

这种情况的例子如下（为了示例更清晰，无关信息用点代替。第一行为下标）：

$x=1$，$p_{min}=2$，$p_{max}=3$，$mn=5$，$mx=7$.

i | 1 2 3 4 5 6 7 8
-------------------
p | . 1 . . . . 2 .
q | . . 1 . 2 . . .

若一个区间的 $\mathrm{MEX}$ 值为 $x+1$，那么它一定要包含 $[p_{min},p_{max}]$ 这个区间，并且它不能包含 $[mn,mx]$ 这个区间（因为一旦包含了，那 $\mathrm{MEX}$ 就一定 $\ge x+1$ 了）。

所以满足这种情况的区间数为：$p_{min}\cdot (mn-p_{max})$，上面示例计算出来为 $2\cdot 2=4$.

• 情况二：$mx<p_{min}$

这种情况的例子如下：

$x=1$，$p_{min}=6$，$p_{max}=7$，$mn=2$，$mx=3$.

i | 1 2 3 4 5 6 7 8
-------------------
p | . . 2 . . 1 . .
q | . 2 . . . . 1 .

满足这种情况的区间数为：$(p_{min}-mx)\cdot (n-p_{max}+1)$，上面示例计算出来为 $3\cdot 2=6$.

• 情况三：$mn<p_{min}$ 且 $p_{max}<mx$

这种情况非常容易漏掉，导致这道题后面的测试点过不去，例子如下：

$x=1$，$p_{min}=4$，$p_{max}=5$，$mn=2$，$mx=8$.

i | 1 2 3 4 5 6 7 8
-------------------
p | . 2 . 1 . . . .
q | . . . . 1 . . 2

由于这种情况 $[p_{min},p_{max}]$ 被包含在 $[mn,mx]$ 里面了，若一个区间 $[l,r]$ 的 $\mathrm{MEX}$ 值为 $x+1$，只需要保证 $mn<l\le p_{min}$ 且 $p_{max}\le r<mx$ 即可。

满足这种情况的区间数为：$(p_{min}-mn)\cdot (mx-p_{max})$，上面示例计算出来为 $2\cdot 3=6$.

• 其他情况

除了上述三种情况，其他情况均不成立，即答案是 $0$. 具体为什么不成立可以举几个例子看。

---

上面是从 $x$ 到 $x+1$ 的思路，那么首先需要初始化一个初值。由于初始时，不存在上一个数的限制，即不存在 $p_{min},p_{max}$ 的限制，因此初始化时，上述三种情况均成立。

另外还需要额外 $+1$，代表取全部序列 $\mathrm{MEX}=n+1$ 的情况（当然这个不一定非要写到初始化里，也能在后面加上 $1$）.

找到 $p,q$ 序列里 $1$ 这个数的位置，记靠左的位置为 $mn$，靠右的位置为 $mx$. 那么初始情况为：

$$\begin{array}{rl}an{s}_{\text{init}}=& \frac{1}{2}(n-mx)(n-mx+1)\\ +& \frac{1}{2}(mn-1)mn\\ +& \frac{1}{2}(mx-mn-1)(mx-mn)\\ +& 1\end{array}$$

代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

void solve()
{
    int n;
    cin >> n;
    vector<int> rp(n + 10), rq(n + 10);
    for (int i = 1; i <= n; i++)
    {
        int t;
        cin >> t;
        rp[t] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        int t;
        cin >> t;
        rq[t] = i;
    }
    int pmin = min(rp[1], rq[1]), pmax = max(rp[1], rq[1]);
    int ans = (n - pmax) * (n - pmax + 1) / 2 +
              (pmin - 1) * pmin / 2 +
              (pmax - pmin - 1) * (pmax - pmin) / 2 + 1;
    for (int i = 2; i <= n; i++)
    {
        int mn = min(rp[i], rq[i]);
        int mx = max(rp[i], rq[i]);
        if (pmax < mn)
            ans += (mn - pmax) * pmin;
        else if (mx < pmin)
            ans += (pmin - mx) * (n - pmax + 1);
        else if (mn < pmin && mx > pmax)
            ans += (pmin - mn) * (mx - pmax);
        pmax = max(pmax, mx);
        pmin = min(pmin, mn);
        if (pmax == n && pmin == 1)
            break;
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}