get();
n = len;
rmqinit();
for(int i = 1; i <= m; i++)
{
int x, y;
x= in();
y = in();
int u = h[x];
int v = h[y];
if(u == v) out(y - x + 1);
else if(u == v - 1) out(max(p[u].right - x + 1, y - p[v].left + 1));
{
int ans = max(p[u].right - x + 1, y - p[v].left + 1);
int t = rmqmax(u + 1, v - 1);
ans = max(ans, t);
out(ans);
}
putchar('\n');
}
}
return 0;
}