// Gemimi 3 Pro preview #include #include #include using namespace std; // 各テストケースを解く関数 void solve() { int N; if (!(cin >> N)) return; // 順列 P の入力 vector P(N); // 値 x が配列 P のどのインデックスにあるかを記録する配列 vector pos(N + 1); for (int i = 0; i < N; ++i) { cin >> P[i]; pos[P[i]] = i; } // current_k: 現在の境界の数(隣り合う要素の High/Low が異なる箇所の数) // max_k: 境界の数の最大値 int current_k = 0; int max_k = 0; // V を 1 から N まで変化させていくシミュレーション // 初期状態 (V=0) では全員 High (1) なので境界は 0 個 // ループの各ステップ x では、値 x が High(1) から Low(0) に変化する for (int x = 1; x <= N; ++x) { int i = pos[x]; // 値 x のインデックス // 左隣 (P[i-1]) との関係を更新 if (i > 0) { // P[i-1] < x ならば、P[i-1] はすでに Low(0) になっている // P[i-1] > x ならば、P[i-1] はまだ High(1) である if (P[i - 1] < x) { // 左隣は 0。自分は 1 -> 0 になる。 // 以前の状態: 0(左) - 1(自分) -> 境界あり // 新しい状態: 0(左) - 0(自分) -> 境界なし current_k--; } else { // 左隣は 1。自分は 1 -> 0 になる。 // 以前の状態: 1(左) - 1(自分) -> 境界なし // 新しい状態: 1(左) - 0(自分) -> 境界あり current_k++; } } // 右隣 (P[i+1]) との関係を更新 if (i < N - 1) { if (P[i + 1] < x) { // 右隣は 0。自分は 1 -> 0 になる。 // 以前: 1 - 0 -> 境界あり // 新規: 0 - 0 -> 境界なし current_k--; } else { // 右隣は 1。自分は 1 -> 0 になる。 // 以前: 1 - 1 -> 境界なし // 新規: 0 - 1 -> 境界あり current_k++; } } // 最大値を更新 if (current_k > max_k) { max_k = current_k; } } // 答えは (境界の最大数 + 1) // ※ブロックの数 = 境界の数 + 1 cout << max_k + 1 << "\n"; } int main() { // 高速化設定 ios::sync_with_stdio(false); cin.tie(nullptr); int T; if (cin >> T) { while (T--) { solve(); } } return 0; }