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 while !Mike can instantly tell the value of .
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 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 a1, a2, …, an ( - 109 ≤ ai ≤ 109) — the sequence a.
The third line contains n integer numbers b1, b2, …, bn ( - 109 ≤ bi ≤ 109) — the sequence b.
Output Print the only integer number — the number of occasions the robot will count, thus for how many pairs is satisfied.
Examples
input 6 1 2 3 2 1 4 6 7 1 2 3 2
output 2
input 3 3 3 3 1 1 1
output 0
Note
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.
题意：给定两个序列A、B，问存在多少个连续子序列，满足max{A}=min{B}？
思路：考虑max{A}<=min{B}的情况，如果满足max{A}<=min{B}，那么这个序列的子序列一定也满足，这样就满足单调性；那么我们就可以枚举区间右端点，去二分左端点，满足max{A}=min{B}的应该是一个区间，所以我们应该分别运用>=和<=去二分出这个区间的左右断点，将差值累加到结果中。这里还需要查询区间最大值，一开始我是用线段树写的，不过好像是被卡常数，超时了，后来改为了可以O(1)查询RMQ，就AC了。
code:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAXN 202000 #define INF 0x3f3f3f3f int n; int ma[MAXN][20],mi[MAXN][20]; void cal() { for(int j=1;(1<<j)<=n;j++) { for(int i=0;i+(1<<j)-1<n;i++) { ma[i][j] = max(ma[i][j-1],ma[i+(1<<(j-1))][j-1]); mi[i][j] = min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]); } } } int RMQmax(int li,int ri) { int k = 0; while((1<<(k+1)) <= ri-li+1) k++; return max(ma[li][k],ma[ri-(1<<k)+1][k]); } int RMQmin(int li,int ri) { int k = 0; while((1<<(k+1)) <= ri-li+1) k++; return min(mi[li][k],mi[ri-(1<<k)+1][k]); } int main() { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&ma[i][0]); for(int i=0;i<n;i++) scanf("%d",&mi[i][0]); cal(); long long ans = 0; int l,r,ma,mb,st,ed; for(int i=0;i<n;i++) { l = i; r = n-1; st = -1; while(l<=r) { int mid = (l+r)>>1; ma = RMQmax(i,mid); mb = RMQmin(i,mid); if(ma >= mb) { if(ma == mb) st = mid; r = mid-1; } else l = mid+1; } if(st == -1) continue; l = i; r = n-1; ed = -1; while(l<=r) { int mid = (l+r)>>1; ma = RMQmax(i,mid); mb = RMQmin(i,mid); if(ma > mb) r = mid-1; else { if(ma == mb) ed = mid; l = mid+1; } } ans += (ed - st + 1); } printf("%I64d\n",ans); return 0; }