2272 - Friends and Subsequences

2272.Friends and Subsequences

Time Limit: 1s Memory Limit: 256MB

Mike and !Mike are old childhood rivals, they are opposite in everything they do, except programming. Today they have a problem they cannot solve on their own, but together (with you)- who knows? Every one of them has an integer sequences a and b of length n. Being given a query of the form of pair of integers (l,r), Mike can instantly tell the value of $2272_1.png$ while !Mike can instantly tell the value of $2272_2.png$ .Now suppose a robot (you!) asks them all possible different queries of pairs of integers (l,r) (1 \le l \le r \le n) (so he will make exactly n(n+1)/2 queries) and counts how many times their answers coincide, thus for how many pairs $2272_3.png$ is satisfied.How many occasions will the robot count?

Input Format(From the terminal/stdin)

Input The first line contains only integer n (1 \le n \le 200000).The second line contains n integer numbers a1,a2,...,an (-109 \le ai \le 109)- the sequence a.The third line contains n integer numbers b1,b2,...,bn (-109 \le bi \le 109)- the sequence b.

Output Format(To the terminal/stdout)

Output Print the only integer number- the number of occasions the robot will count, thus for how many pairs $2272_3.png$ is satisfied.

Sample Input 1

Copy

6
1 2 3 2 1 4
6 7 1 2 3 2
 \n
 · · · · · \n
 · · · · · \n

Sample Output 1

Copy

2
 \n

Sample Input 2

Copy

3
3 3 3
1 1 1
 \n
 · · \n
 · · \n

Sample Output 2

Copy

0
 \n

Hints

The occasions in the first sample case are:1.l=4,r=4 since max{2}=min{2}.2.l=4,r=5 since max{2,1}=min{2,3}.There are no occasions in the second sample case since Mike will answer 3 to any query pair, but !Mike will always answer 1.

Submit

请先登录

Submit

题解(0)