A player's score is equal to the number of distinct values in their inventory after all numbers have been picked. Therefore, Jong should always prioritize obtaining values that maximize the number of distinct values in his inventory.

Each distinct value belongs to one of two categories:

1. It appears exactly once in the entire array.
2. It appears at least twice.

If a value appears exactly once, then whichever player picks it permanently gains one point, since the other player can never obtain that value. On the other hand, if a value appears at least twice, then regardless of who picks the first occurrence, Jong can always obtain another occurrence later if he has not collected that value yet. Thus, every non-unique value can always contribute one point to Jong's final score.

Since the opponent wants to minimize Jong's score, they will always contest the remaining unique values whenever possible. Therefore, all unique values are effectively picked alternately between the two players.

Because Jong moves first, he obtains ⌈U / 2⌉ of the U unique values.

Let M denote the number of values appearing at least twice. Jong eventually obtains every one of these values, contributing M additional points.

So, the answer is ⌈U / 2⌉ + M.

1. Count the frequency of every value.
2. Let U be the number of values whose frequency is exactly 1.
3. Let M be the number of values whose frequency is at least 2.
4. Output ⌈U / 2⌉ + M.

• Time Complexity: O(N)
• Space Complexity: O(N)

Here are some valid solutions:

#include <stdio.h>

int main(){
    int n;
    scanf("%d",&n);
    int a[n],freq[1000010] = {0};
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        freq[a[i]]++;
    }
    int u=0,m=0;
    for(int i=0;i<1000010;i++){
        if(freq[i]==1){
            u++;
        }
        else if(freq[i]>1){
            m++;
        }
    }
    printf("%d",(u+1)/2+m);
}

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> freq(1000010, 0);
    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        freq[x]++;
    }
    int u = 0, m = 0;
    for(int x : freq){
        if(x == 1){
            u++;
        }
        else if(x > 1){
            m++;
        }
    }
    cout << (u + 1) / 2 + m;
}