Note.ms

#include <bits/stdc++.h>
#define int long long
#define popc __builtin_popcount
#define ctz __builtin_ctz
//#define DEBUG
using namespace std;

struct node {
  int mn, mx, ms;
}d[5000050];

int t, n, q, arr[2000020], a, b;

void pushup(int id, int l, int r) {
  d[id].mn = min(d[id * 2].mn, d[id * 2 + 1].mn);
  d[id].mx = max(d[id * 2].mx, d[id * 2 + 1].mx);
  d[id].ms = max(d[id * 2].ms, d[id * 2 + 1].ms);
  if(d[id * 2].mx > d[id * 2 + 1].mn) d[id].ms = r - l + 1;
}

void build(int id = 1, int l = 1, int r = n) {
  if(l == r) {
    d[id] = {arr[l], arr[l], 1};
    return ;
  }
  int mid = (l + r) >> 1;
  build(id * 2, l, mid);
  build(id * 2 + 1, mid + 1, r);
  pushup(id, l, r);
}

void modify(int x, int v, int id = 1, int l = 1, int r = n) {
  if(l == r) {
    arr[l] = v;
    d[id] = {arr[l], arr[l], 1};
    return ;
  }
  int mid = (l + r) >> 1;
  if(x <= mid) modify(x, v, id * 2, l, mid);
  else modify(x, v, id * 2 + 1, mid + 1, r);
  pushup(id, l, r);
}

signed main() {
#ifndef DEBUG
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
#endif
  for(cin >> t; t--; ) {
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> arr[i];
    for(; popc(n) != 1; arr[++n] = 1000000000);
    build();
    cout << (d[1].ms >> 1) << '\n';
    for(; q--; ) {
      cin >> a >> b;
      a++;
      modify(a, b);
      cout << (d[1].ms >> 1) << '\n';
    }
  }
  return 0;
}

Note.ms/CF383362323