题目连接：https://ac.nowcoder.com/acm/contest/881/A

题意

对于两个数组区间l,r ，rmq相等的定义是：对于l,r内任意子区间rmq值的对应数组下标都相等（即任意子区间的最小值对应的下标都相等），那么这两个数组的l,r区间RMQ相等。

现在问你给你两个序列，存在若干R，能使两个序列下标1~R的区间的rmq相等，现在问你最大的R值是多少。

解释一下样例：

样例三
5
3 1 5 2 4
5 2 4 3 1

很明显，对于从1~4的区间，两个序列的任意子序列的rmq所对应的下标值都相同，

但是在1~5区间：

序列1所对应的最小值是1，值所对应的下标值是2。

序列2所对应的最小值是1，值所对应的下标值是5.

下标值并不相同，所以R最大只能为4

思路

比赛中：

线段树一顿操作，又RE又TLE又WA。

事实上：

每个元素可以影响到RMQ值的区间为,而由RMQ的性质可知，其最只能影响所有比他大的值，而若遇见了一个比其值小的值,则其无法影响包含的区间。

由于我们是求1~r的区间，我们只需要对于每个插入元素进行向前搜索,观察其在其之间究竟能影响多少元素，由上文可知，若对于元素,在其之前存在元素，且元素，且在，j到i之间的所有元素均大于(即找到第一个比小的元素，即第一个不能影响的元素),则元素的影响范围只能到,即元素i的影响范围是,注意这里的.

那么我们只需要记录一下对于每个元素其能在其之前所能影响到的最大范围的序列下标值，之后将两个数组比对一下。若两个序列的前r区间RMQ性质相同，则其所算出的前文的记录值序列也应相同。找到第一个不相同的位置的前一个位置即为答案。

代码实现使用栈进行维护一个单调递增的序列，对于每个新插入的元素将其前面比起值大的元素从栈中移除，则未移除的第一个元素的下标值即为上文中我们需要记录的记录值。

不难发现，若下一个元素比前一元素小，则当前元素删除的值即使不删除对于下一元素也毫无意义(不删除就会跳过，但是没啥意义)，也会被删除，若下一元素元素值比前一元素大，则下意元素的影响范围只有其本身，其只需记录最大范围的下标值即为当前元素的坐标即可。即当前元素i到记录值j之间的元素在比对大小之后均无意义，可剔除。

AC代码

/* ***********************************************
Author :Chord
Email:pengrj2018@gmail.com
Created Time :2019/7/19 13:56:15
File Name :new.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <stack>
#include <bitset>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int maxn = 5e5 + 7;
int n;
vector<int> solve(void)
{
    vector<pii>p;
    vector<int>ans(n);
    p.emplace_back(0,-1);
    for(int i = 0 ;i < n ;i++){
        int a;
        cin>>a;
        while(p.back().first > a)
            p.pop_back();
        ans[i] = p.back().second;
        p.emplace_back(a,i);
    }
    return ans;
}

int main(void)
{
    while(cin>>n){
        vector<int> a = solve();
        vector<int> b = solve();
        int l = 0;
        while(l < n && a[l] == b[l])
            l++;
        cout<<l<<endl;
    }
    return 0;
}