题目大意

定义一个数组为 “脆弱的”（vulnerable），如果可以通过反复对任意子数组应用 Stalin 排序（一种幽默的排序算法：从左到右扫描，保留严格递减的元素，删除其余元素），最终使整个数组变为 非递增（即 $a_1 \ge a_2 \ge \dots \ge a_n$）。

给定一个长度为 $n$ 的数组 $a$，你可以删除其中的任意个元素（不改变剩余元素的相对顺序）。问最少删除多少个元素，可以使剩下的数组变成脆弱的。

---

关键结论

一个数组是脆弱的，当且仅当它的第一个元素是全局最大值。

证明

• 充分性：若第一个元素是最大值，则对整个数组执行一次 Stalin 排序。因为第一个元素最大，后续元素如果比当前保留的最后一个元素小则保留，否则删除。最终结果一定非递增（实际上就是原数组的一个非递增子序列，且第一个元素始终保留）。所以一次操作即可，数组脆弱。

• 必要性：若第一个元素不是最大值，设最大值出现在位置 $k>1$ 且 $a_k > a_1$。注意，对任意子数组执行 Stalin 排序时：

  • 子数组的第一个元素永远不会被删除（因为它作为起点被保留）。
  • 全局最大值 $a_k$ 也永远不会被删除（因为每次比较时它都大于之前的保留元素，所以它自己会被保留）。

  因此，无论进行多少次操作，$a_1$ 和 $a_k$ 始终会被保留在数组中，且 $a_1 < a_k$，最终数组不可能变成非递增。故数组不脆弱。

---

问题转化

要使数组脆弱，必须通过删除一些元素，使得剩余数组的第一个元素成为该数组的最大值。

换句话说，我们需要找到一个 子序列（保留原顺序），使得该子序列的第一个元素是子序列中的最大值。我们想保留尽可能多的元素（即删除最少），因此需要找到 最长的满足上述条件的子序列。

设这个最长长度为 $L$，则最少删除数为 $n - L$。

---

如何求 $L$？

固定子序列的第一个元素在原数组中的位置 $i$（$0 \le i < n$）。
为了满足“第一个元素是最大值”，我们需要：

• 删除所有在 $i$ 之前 的元素（否则它们会成为新的第一个元素，破坏条件）。
• 删除所有在 $i$ 之后 且值 大于 $a_i$ 的元素（因为它们会大于第一个元素）。
• 保留 $a_i$ 本身，以及所有在 $i$ 之后 且值 不超过 $a_i$ 的元素（不论它们的相对顺序如何）。

这样保留的元素个数为：

$$\text{count}_i = \#\{j \mid i \le j < n \text{ 且 } a_j \le a_i\} $$

即从 $i$ 开始到末尾，值不大于 $a_i$ 的元素个数。

因此，最长满足条件的子序列长度为：

$$L = \max_{0 \le i < n} \text{count}_i$$

最终答案为：

$$\text{ans} = n - L$$

---

算法实现

直接按照上述公式计算即可，时间复杂度 $O(n^2)$，空间 $O(1)$。

由于题目保证 $\sum n \le 2000$，$O(n^2)$ 完全可行。

代码（标程）

#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        int best = 0;
        for (int i = 0; i < n; ++i) {
            int cnt = 0;
            for (int j = i; j < n; ++j) {
                if (a[j] <= a[i]) ++cnt;
            }
            best = max(best, cnt);
        }
        cout << n - best << "\n";
    }
    return 0;
}

---

复杂度分析

• 时间复杂度：$O\left(\sum n^2\right)$，最坏情况下 $2000^2 = 4\times 10^6$，完全可行。
• 空间复杂度：$O(n)$ 用于存储数组。

---

样例验证

以第一个测试用例 [3,6,4,9,2,5,2] 为例：

• $i=0$，$a_0=3$，后面 $\le 3$ 的有 $3,2,2$ → 3 个
• $i=1$，$a_1=6$，后面 $\le 6$ 的有 $6,4,2,5,2$ → 5 个
• $i=2$，$a_2=4$，后面 $\le 4$ 的有 $4,2,2$ → 3 个
• $i=3$，$a_3=9$，后面 $\le 9$ 的有 $9,2,5,2$ → 4 个
• $i=4$，$a_4=2$，后面 $\le 2$ 的有 $2,2$ → 2 个
• $i=5$，$a_5=5$，后面 $\le 5$ 的有 $5,2$ → 2 个
• $i=6$，$a_6=2$，后面 $\le 2$ 的有 $2$ → 1 个

最大值 $best = 5$，答案 $= 7 - 5 = 2$，与样例输出一致。

---

扩展：$O(n \log n)$ 解法（Bonus）

对于每个 $i$，我们需要快速计算从 $i$ 开始有多少个元素 $\le a_i$。
若我们将数组从右向左处理，维护一个数据结构（如 Fenwick 树或有序集合）来记录已经遍历过的元素值及其出现次数。
对于当前 $i$，查询值域 $[-\infty, a_i]$ 的元素个数即可得到 $\text{count}_i$。
这需要先将 $a$ 离散化（值域 $10^9$ 但 $n\le 2000$），然后树状数组单点更新、前缀查询，复杂度 $O(n \log n)$。

---

总结

本题的核心在于发现 脆弱数组等价于第一个元素为最大值，从而将问题转化为寻找最长的以某个元素开头且该元素不小于其后所有元素的子序列。通过枚举起点并统计后面不超过它的元素个数，即可得到最优解。