#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5010;
int n, q, a[N], b[N], l, r, stk[N], tot, ans, pt[N];
struct node {
	int l, r, id;
} buf[N];

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	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 <= q; i++) {
		cin >> l >> r;
		buf[i] = {l, r, i};
	}
	for (int i = 1; i <= n; i++) {
		for (int k = 1; k <= q; k++) {
			if (buf[k].l != i) continue;
			int R = buf[k].r, id = buf[k].id;
			ans = 0, tot = 0;
			for (int j = i; j <= R; j++) {
				while (1) {
					if (!tot || (a[stk[tot]] != a[j] && b[stk[tot]] > b[j])) {
						stk[++tot] = j;
						break;
					}
					--tot;
				}
				if (tot == 1) ++ans;
			}
			pt[id] = ans;
		}
	}
	for (int i = 1; i <= q; i++) cout << pt[i] << "\n";
	return 0;
}