https://ac.nowcoder.com/acm/contest/881/A

题意:给定两个长度为n(1e5)的排列a,b,求最大的m

使a,b的前缀[1,m]的所有子区间的最小值的下标相同

分析:对a,b来说，每个区间都对应着一个确定的下标，相反地，每个下标都对应着一些区间，这些区间

是可以求出来的,利用单调栈求出min(le),max(ri)使 a[le,ri]>=a[i],这样对应的区间就是{[k1,k2]|le<=k1<=i<=k2<=ri}

既然题目说前缀中每个区间对应的下标是要相同地，那么反过来，每个下标对应的m以内的区间要全部相同。

那么就相当于[1,m]的每个元素的le和min(m,ri)要相同。

再简化一下，由于是对所有元素都有这个要求，所以我们最后只要判断一下le是不是全部相同就可以了‘

/////////////////////////////////////////Info/////////////////////////////////////////////////
//Problem:
//Date:
//Skill:
//Bug:
/////////////////////////////////////////Definations/////////////////////////////////////////////////
//循环控制
#define CLR(a) memset((a),0,sizeof(a))
#define F(i,a,b) for(int i=a;i<=int(b);++i)
#define F2(i,a,b) for(int i=a;i>=int(b);--i)
#define RE(i,n)  for(int i=0;i<int(n);i++)
#define RE2(i,n) for(int i=1;i<=int(n);i++)
//简化敲击
#define PII pair<int,int>
#define PDD pair<double,double>
#define PLL pair<long long ,long long>
#define PB push_back
#define MODY(n) (n%=mod)<0?n+=mod:n
#define MODED(n) ((n)<0?(n)%mod+mod:(n)%mod)
#define x first
#define y second
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const long long llinf = 0x3f3f3f3f3f3f3f3f;
////////////////////////////////////////Options//////////////////////////////////////////////////////
#define stdcpph
#define CPP_IO

#ifdef stdcpph
#include<bits/stdc++.h>
#else
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
#ifdef CPP_IO
#include<iostream>
#include<iomanip>
#include<string>
#else
#include<stdio.h>
#endif
#endif
////////////////////////////////////////Basic Functions//////////////////////////////////////////////
template<typename INint> inline void IN(INint &x)
{
	x = 0; int f = 1; char c; cin.get(c);
	while (c<'0' || c>'9') { if (c == '-')f = -1; cin.get(c); }
	while (c >= '0'&&c <= '9') { x = x * 10 + c - '0'; cin.get(c); }
	x *= f;
}
template<typename INint> inline void OUT(INint x)
{
	if (x > 9)OUT(x / 10); cout.put(x % 10 + '0');
}
////////////////////////////////////////Added Functions//////////////////////////////////////////////
const int maxn = int(1e5+8);
int a[2][maxn], L[2][maxn];
int B[2][maxn];
//2_3-单调栈
int n;
int mode = 1;
bool da(int a, int b) { return a > b; }
bool xiao(int a, int b) { return a < b; }
//A[i]存储h[i]左边第一个不满足cmp(h[j],h[i])的j,或者def
void init(int n, int h[], int A[], bool cmp(int, int), int def)
{
	stack<int>S; S.push(def);
	RE2(i, n)
		//F2(i,n,1)
	{
		while (S.top() != def
			&& cmp(h[S.top()], h[i]))//TODO:大于(<=h[i])还是小于(>=h[i])
			S.pop();
		A[i] = S.top(); S.push(i);
	}
}
////////////////////////////////////////////Code/////////////////////////////////////////////////////
int main()
{
	//freopen("C:\\Users\\VULCAN\\Desktop\\data.in", "r", stdin);
	int T(1), cas(0);
#ifdef CPP_IO// CPP_IO
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//cin >> T;
#else
	//IN(T);
#endif 
	/////////////////////////////////////////////////////////////////////////////////////////////////
	while (cas, T--,cin>>n)
	{
		F(id, 0, 1)
		{
			F(i, 1, n)cin >> a[id][i];
			mode = 1;
			init(n, a[id], B[id], da, 0);
			mode = 0;
			init(n, a[id], L[id], xiao, 0);
		}
		int ans(0);
		while ((ans + 1 != n + 1) && B[0][ans + 1] == B[1][ans + 1])++ans;
		cout << ans << endl;
	}
	///////////////////////////////////////////////////////////////////////////////////////////////////
	return 0;
}
//What to Debug
/*
-1.最好把全部warning都X掉,否则:https://vjudge.net/solution/19887176
0.看看自己是否有可能需要快读，禁endl
1.数组越界，爆int,浮点精度(查看精度是否达到题目要求,看有没有浮点数比较:eps)，取模操作，初始化数组，边缘数据,输出格式(cas)
2.通读代码，代码无逻辑错误
3.读题，找到题意理解失误或算法错误
4.放弃
*/