2229D

我们发现出现类似于“最小值最大”的形式，考虑这个值是不是单调的。

如果 x 可行，那么可以考虑更大的。

如果 x 不可行，那么更大的就不用考虑。

符合单调性，可以二分答案。

如何检验 x 是否可行？

将每个数字，大于等于 x 的设为 1，其它设为 0.

此时如何进行合并，使得合并后剩下 1, 1

如果四个都是 1，那么合并后就剩下了两个 1，1 在减少，对局面不利。

相反，如果都是 0，那么合并后就少了两个 0，对局面有利。

而其它情况不会造成 1，0 的失衡，0, 0 和 0, 1 合成还是 0, 0，我们只需要统计包含 0, 0 的区间个数和 1, 1 的个数即可。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
using pii = pair<int, int>;

void solve() {
  int n;
  cin >> n;
  vector<pii> a(n);
  int minn = 1e9, maxn = -1;
  for (int i = 0; i < n * 2; i++) {
    int x;
    cin >> x;
    minn = min(minn, x);
    maxn = max(maxn, x);
    if (i < n) {
      a[i].fi = x;
    } else {
      a[i - n].se = x;
    }
  }
  int l = minn, r = maxn + 1;
  auto check = [&](int x) {
    int cnt0 = 0, cnt1 = 0;
    int i = 0;
    while (i < n) {
      bool ok = false;
      while (i < n && (a[i].fi < x || a[i].se < x)) {
        if (a[i].fi < x && a[i].se < x) ok = true;
        i++;
      }
      if (ok) cnt0++;
      if (i < n) cnt1++, i++;
    }
    return cnt1 > cnt0;
  };
  while (l < r) {
    int mid = (l + r) >> 1;
    if (check(mid)) {
      l = mid + 1;
    } else {
      r = mid;
    }
  }
  cout << l - 1 << '\n';
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--) solve();
  return 0;
}