#include <bits/stdc++.h>
#define int long long
#define maxn 500005
#define second second
using namespace std;
int n, q, l, r;
int a[maxn], b[maxn];
deque<pair<pair<int, int>, int> > st;
int nxt[21][maxn];
signed main() {
	freopen("stack.in", "r", stdin);
	freopen("stack.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	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++) {
		while(!st.empty() && (st.back().first.first == a[i] || st.back().first.second <= b[i])) {
			nxt[0][st.back().second] = i;
			st.pop_back();
		}
		st.push_back({{a[i], b[i]}, i});
	}
	for(int i = 1; i <= 20;i++) {
		for(int j = 1; j <= n; j++) {
			nxt[i][j] = nxt[i - 1][nxt[i - 1][j]];
		}
	}
	int cnt = 1;
	while(q--) {
		cin >> l >> r;
		int i = l;
		for(int step = 20; step >= 0; step--) {
			if(nxt[step][i] && nxt[step][i] <= r) {
				cnt += (1 << step);
				i = nxt[step][i];
			}
		}
		cout << cnt << endl;
		cnt = 1;
	}
	return 0;
}