C - Friends and Subsequences

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

Input

3

3 3 3

1 1 1

Output

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.

求区间最大值和最小值相同的区间有多少个，因为区间越长，最大值越大，最小值越小，所以可以二分找

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include <iomanip>

#include<cmath>

#include<float.h>

#include<string.h>

#include<algorithm>

#define sf scanf

#define pf printf

#include<vector>

#include<queue>

using namespace std;

#define rep(i,a,n) for (int i=a;i<n;i++)

#define per(i,a,n) for (int i=a;i>=n;i--)

#define scf(x) scanf("%d",&x)

#define scff(x,y) scanf("%d%d",&x,&y)

#define prf(x) printf("%d\n",x)

#define mm(x,b) memset((x),(b),sizeof(x))

typedef long long ll;

const ll mod=1e9+7;

const double eps=1e-8;

const int inf=0x3f3f3f3f;

const double pi=acos(-1.0);

const int N=2e5+3;

int a[N],b[N];

int dpmax[N][20],dpmin[N][20];

void first(int n)

{

	mm(dpmax,0);

	mm(dpmin,0);

	rep(i,1,n+1)

	{

		dpmax[i][0]=a[i];

		dpmin[i][0]=b[i];

	}

	for(int j=1;(1<<j)<=n;j++)

	{

		for(int i=1;i+(1<<j)-1<=n;i++)

		{

			dpmax[i][j]=max(dpmax[i][j-1],dpmax[i+(1<<(j-1))][j-1]);

			dpmin[i][j]=min(dpmin[i][j-1],dpmin[i+(1<<(j-1))][j-1]);

		}

	}

}

int fmax(int l,int r)

{

	int x=0;

	while(l-1+(1<<x)<=r) x++;

	x--;

	return max(dpmax[l][x],dpmax[r-(1<<x)+1][x]);

}

int fmin(int l,int r)

{

	int x=0;

	while(l-1+(1<<x)<=r) x++;

	x--;

	return min(dpmin[l][x],dpmin[r-(1<<x)+1][x]);

}

int main()

{

	ll ans=0;

	int n,le,ri,mid;

	scf(n);

	rep(i,1,n+1)

	scf(a[i]);

	rep(i,1,n+1)

	scf(b[i]);

	first(n);

	rep(i,1,n+1)

	{

		int l=-1,r=-1;

		le=i;

		ri=n;

		while(ri>=le)

		{

			mid=(le+ri)/2;

			if(fmax(i,mid)>=fmin(i,mid))

			{

				if(fmax(i,mid)==fmin(i,mid))

					l=mid;

				ri=mid-1;

			}

			else

			le=mid+1;

		}

		if(l==-1) continue;

		le=i;ri=n;

		while(ri>=le)

		{

			mid=(le+ri)/2;

			if(fmax(i,mid)<=fmin(i,mid))

			{

				if(fmax(i,mid)==fmin(i,mid))

				r=mid;

				le=mid+1;;

			}else

			ri=mid-1;

		}

		ans+=r-l+1;

	}

	cout<<ans<<endl;

	return 0;

}

巴特西

C - Friends and Subsequences

Input

Output

Input

Output

Input

Output

Note

求区间最大值和最小值相同的区间有多少个，因为区间越长，最大值越大，最小值越小，所以可以二分找

最新文章

热门文章