2111: CF689 - D. Friends and Subsequences
[Creator : ]
Description
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 $\text{max}_{i=l}^r a_i$ while !Mike can instantly tell the value of $\text{min}_{i=l}^r b_i$.
Now suppose a robot (you!) asks them all possible different queries of pairs of integers $(l,r)\ (1≤l≤r≤n)$ (so he will make exactly $n(n+1)/2$ queries) and counts how many times their answers coincide, thus for how many pairs $\text{max}_{i=l}^r {a_i}=\text{min}_{i=l}^r {b_i}$ is satisfied.
How many occasions will the robot count?
Now suppose a robot (you!) asks them all possible different queries of pairs of integers $(l,r)\ (1≤l≤r≤n)$ (so he will make exactly $n(n+1)/2$ queries) and counts how many times their answers coincide, thus for how many pairs $\text{max}_{i=l}^r {a_i}=\text{min}_{i=l}^r {b_i}$ is satisfied.
How many occasions will the robot count?
Input
The first line contains only integer $n\ (1≤n≤200,000)$.
The second line contains $n$ integer numbers $a_1,a_2,...,a_n\ (-10^9≤a_i≤10^9)$ − the sequence $a$.
The third line contains $n$ integer numbers $b_1,b_2,...,b_n\ (-10^9≤b_i≤10^9)$ − the sequence $b$.
The second line contains $n$ integer numbers $a_1,a_2,...,a_n\ (-10^9≤a_i≤10^9)$ − the sequence $a$.
The third line contains $n$ integer numbers $b_1,b_2,...,b_n\ (-10^9≤b_i≤10^9)$ − the sequence $b$.
Output
Print the only integer number− the number of occasions the robot will count, thus for how many pairs $\text{max}_{i=l}^r {a_i}=\text{min}_{i=l}^r {b_i}$ is satisfied.
Sample 1 Input
6
1 2 3 2 1 4
6 7 1 2 3 2
Sample 1 Output
2
l=4,r=4 since max{2}=min{2}.
l=4,r=5 since max{2,1}=min{2,3}.
l=4,r=5 since max{2,1}=min{2,3}.
Sample 2 Input
3
3 3 3
1 1 1
Sample 2 Output
0
since Mike will answer 3 to any query pair, but !Mike will always answer 1.