CF1793D.Moscow Gorillas
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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≤l≤r≤n ) such that MEX([pl,pl+1,…,pr])=MEX([ql,ql+1,…,qr]) .
The MEX of the sequence is the minimum integer positive number missing from this sequence. For example, MEX([1,3])=2 , MEX([5])=1 , MEX([3,1,2,6])=4 .
You do not want to risk your health, so you will not dare to refuse the gorillas.
输入格式
The first line contains a single integer n ( 1≤n≤2⋅105 ) — the permutations length.
The second line contains n integers p1,p2,…,pn ( 1≤pi≤n ) — the elements of the permutation p .
The third line contains n integers q1,q2,…,qn ( 1≤qi≤n ) — the elements of the permutation q .
输出格式
Print a single integer — the number of suitable pairs l and r .
输入输出样例
输入#1
3 1 3 2 2 1 3
输出#1
2
输入#2
7 7 3 6 2 1 5 4 6 7 2 5 3 1 4
输出#2
16
输入#3
6 1 2 3 4 5 6 6 5 4 3 2 1
输出#3
11
说明/提示
In the first example, two segments are correct – [1,3] with MEX equal to 4 in both arrays and [3,3] with 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 MEX(5,4)=MEX(1,4) .