typedef long long int ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef map<ll, ll> mll;

void solve(){
    ll n;
    cin>>n;
    vl v(n);
    for(ll i = 0; i<n; i++) cin>>v[i];
    mll mp;
    for(auto &i:v) mp[i]++;
    ll moves = n/2;

    ll mx = mp.size();
    vvl dp(mx, vl(moves + 1));
    dp[0][0] = 0;
    ll cnt = 0;
    for(auto &[x, y]:mp){
        if(cnt == 0){
            dp[cnt][0] = 0;
            ++cnt;
            continue;
        }
        for(ll j = 0; j<=min(moves, cnt); j++){
            if(dp[cnt - 1][j] || j == cnt){
                if(cnt - dp[cnt - 1][j] >= y){
                    if(j >= y){
                        dp[cnt][j - y] = max(dp[cnt][j - y], dp[cnt - 1][j] + 1);
                    }
                }
                if(j < cnt) dp[cnt][j + 1] = max(dp[cnt][j + 1], dp[cnt - 1][j]);
            }
        }
        ++cnt;
    }
    ll ans = mx;
    for(ll i = 0; i<= moves; i++){
        ans = min(ans, mx - dp[mx - 1][i]);

    }
    cout<<ans<<'\n';
}