D. Permutation Addicts

我们观察给的条件
发现不是那么明朗 我们把x变成ai看看
if a[i]<=k b[a[i]] := a[j] (j<i) && a[j]>k 如果没有就把b[a[i]]:=n+1肯定还是>k的
这不就相当于把b[a[i]]>a[i] 所以我们统计b[i]>i有几个 k就是几
当然可以通过第二个条件 那样统计的就是n-k
然后我们可以发现的是 a[1]因为前面没有东西 所以b[a[1]]=n+1 || b[a[1]]=0
而且n+1和0只会存在一个 因为你要是有0了 就证明前面有大于k的数 反之亦然
所以我们这样就可以直接找出a[1]???
显然不是的 我们观察第二个样例 有n+1 但是有3个
但是后面出现了3个3 这就给了我们一个限制 那就是前面这一段结尾一定是3 这样才是合法的
我们可以开个vector数组 将每个值的下标存下来 因为我们是从前往后做的
要是该vector里面下标有被征用的 比如这里的3
那我们就必须把这个3放在结尾
可以感性理解一下

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
const int M = 998244353;
const int mod = 998244353;
#define int long long
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}

void solve() {
    int n,k=0;cin>>n;
    vector<int>v[n+2],ans,b(n+1);
    for(int i=1;i<=n;i++){
        cin>>b[i];
        k+=b[i]>i;
        v[b[i]].push_back(i);
    }
    int cur=0;
    if(v[n+1].size())cur=n+1;
    while(ans.size()<n){
        for(auto &it:v[cur])
            if(v[it].size())
            {swap(it,v[cur].back());break;}
        ans.insert(ans.end(),v[cur].begin(),v[cur].end());
        cur=v[cur].back();
    }
    cout<<k<<endl;
    for(auto i:ans)cout<<i<<' ';cout<<endl;
}
signed main(){
    fast
    int T;cin>>T;
    while(T--) {
        solve();
    }
    return ~~(0^_^0);
}