#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")



/*
  pair (value, index)
  (a, u) - (b, v) := (a-b, u)
  
  p[0] < p[1] < ... < p[n-1]
  
  Lemma. n >= 2 && p[1] < p[n-1] - p[0] ==> p[n-1] is safe to eat p[0]
    (proof) n = 2 ==> OK
            p[n-2] < p[n-1] - p[0] ==> OK
            p[n-2] does not eat p[1] ==> OK
            p[n-2] eats p[1]:
              p[n-2] - p[1] < p[n-1] - p[0]
              (p[n-1] - p[0]) is eaten in final result ==> (p[n-2] - p[1]) is eaten in final result
              ==> p[n-2] should not have eaten p[1]
  
  in simulation
  round k (0 <= k <= N-2): (a[k], u[k]) eats (b[k], v[k])
    (N-k) snakes ~~> (N-k-1) snakes
  take 0 <= K < L s.t.
    - 0 <= k < K ==> ((a[k], u[k]) - (b[k], v[k])) becomes not min
    - K <= k < L ==> ((a[k], u[k]) - (b[k], v[k])) becomes min (==> u[k] = v[k+1])
    -      k = L ==> ((a[k], u[k]) - (b[k], v[k])) becomes not min
  
  K exists (K <= N-2)
  v[0], ..., v[K-1]: eaten in final result
  
  if no such L exists, L := N-2
  
  - round L: want to eats
  - round L-1: do not wan to eat
  - round L-2: wan to eat
  - ...
  
  - K == L (mod 2): v[K] is eaten, stop at round K+1
  - K != L (mod 2): stop at round K
  
  round [0, K)
    max decreases
    min increases
    0 <= k < K ==> (a[k], u[k]) - (b[k], v[k]) <= (a[k+1], u[k+1]) - (b[k+1] - v[k+1])
*/

using P = pair<int, int>;

int N;
vector<int> A;

int solve() {
  int K = -1, L = -1;
  deque<P> que[3];
  que[0].resize(N);
  for (int i = 0; i < N; ++i) que[0][i] = make_pair(A[i], i);
  for (int k = 0; ; ++k) {
    assert((int)que[0].size() + (int)que[1].size() >= 2);
    const int hMx = (que[0].size() && (!que[1].size() || que[0].back() > que[1].back())) ? 0 : 1;
    const P mx = que[hMx].back();
    que[hMx].pop_back();
    const int hMn = (que[0].size() && (!que[1].size() || que[0].front() < que[1].front())) ? 0 : 1;
    const P mn = que[hMn].front();
    que[hMn].pop_front();
    const P p(mx.first - mn.first, mx.second);
    assert(!que[1].size() || p < que[1].front());
    if (!que[0].size() || p < que[0].front()) {
      K = k;
      que[hMn].push_front(mn);
      que[hMx].push_back(mx);
      break;
    } else {
      que[1].push_front(p);
    }
  }
  que[2].resize((int)que[0].size() + (int)que[1].size());
  merge(que[0].begin(), que[0].end(), que[1].begin(), que[1].end(), que[2].begin());
  for (int k = K; ; ++k) {
    assert((int)que[2].size() >= 2);
    if ((int)que[2].size() == 2) {
      L = k;
      break;
    }
    const P mx = que[2].back();
    que[2].pop_back();
    const P mn = que[2].front();
    que[2].pop_front();
    const P p(mx.first - mn.first, mx.second);
    assert(que[2].size());
    if (p < que[2].front()) {
      que[2].push_front(p);
    } else {
      L = k;
      break;
    }
  }
  return N - (((L - K) & 1) ? K : (K + 1));
}

int main() {
  int T;
  for (; ~scanf("%d", &T); ) {
    scanf("%d", &N);
    A.resize(N);
    for (int i = 0; i < N; ++i) {
      scanf("%d", &A[i]);
    }
    for (int t = 0; t < T; ++t) {
      if (t) {
        int K;
        scanf("%d", &K);
        for (; K--; ) {
          int X, Y;
          scanf("%d%d", &X, &Y);
          --X;
          A[X] = Y;
        }
      }
      const int ans = solve();
      printf("%d\n", ans);
    }
  }
  return 0;
}