#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 100010; int n, m; bool vis[maxn]; int c[maxn], a[maxn], pos[maxn]; struct Query { int l, r, id; bool operator <(const Query &t) const { return l < t.l; } } q[maxn]; int ans[maxn]; inline int sum(int x) { int s = 0; while (x > 0) { s += c[x]; x -= x & -x; } return s; } inline void add(int x, int v) { while (x <= n) { c[x] += v; x += x & -x; } } int main() { int i, j, cas, l, r; scanf("%d", &cas); while (cas--) { scanf("%d%d", &n, &m); for (i = 1; i <= n; i++) { vis[i] = 0; scanf("%d", &a[i]); pos[a[i]] = i; c[i] = 0; } for (i = 0; i < m; i++) { scanf("%d%d", &q[i].l, &q[i].r); q[i].id = i; } l = 1; for(i = 1; i <= n; i++) { add(i, 1 - vis[a[i] - 1] - vis[a[i] + 1]); vis[a[i]] = 1; } sort(q, q + m); for (i = 0; i < m; i++) { while (l < q[i].l) { add(l, -1); vis[a[l]] = 0; if (vis[a[l] - 1]) add(pos[a[l] - 1], 1); if (vis[a[l] + 1]) add(pos[a[l] + 1], 1); l++; } ans[q[i].id] = sum(q[i].r); } for (i = 0; i < m; i++) printf("%d\n", ans[i]); } return 0; } /* */