#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 7;
int n,q,a[N],b[N],ans[5007][5007];
stack<pair<int,int>> z;
bool tp = 1;
int main()
{
    freopen("stack.in","r",stdin);
    freopen("stack.out","w",stdout);
    cin >> n >> q;
    for (int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    for (int i = 1;i <= n;i++)
    {
        cin >> b[i];
    }
    for (int i = 1;i <= n;i++)
    {
        ans[i][i] = 1;
        z.push({a[i],b[i]});
        for (int j = i + 1;j <= n;j++)
        {
            while (!z.empty())
            {
                if (z.top().first == a[j] || z.top().second <= b[j])
                {
                    z.pop();
                }
                else
                {
                    break;
                }
            }
            if (z.empty())
            {
                ans[i][j] = ans[i][j - 1] + 1;
            }
            else
            {
                ans[i][j] = ans[i][j - 1];
            }
            z.push({a[j],b[j]});
        }
        while (!z.empty())
        {
            z.pop();
        }
    }
    for (int i = 1,l,r;i <= q;i++)
    {
        cin >> l >> r;
        cout << ans[l][r] << endl;
    }
    return 0;
}