Author : Kamonasish Roy
Tester : Md Jahirul Islam Hridoy, Emon Thakur, Abu Sufian Rafi, Abid Hussen.
Editorial:
Key observations:
Negative numbers should be avoided

If Roy picks a negative number, it decreases his score.

If Hridoy picks a negative number, it increases Roy's score (since Hridoy subtracts it).

So, both players will avoid negative numbers when possible.

Each player must make at least one move (compulsory)

Even if the board has only negative numbers, both players are forced to make at least one move.

Therefore, the game must continue for at least two turns (one by each player), even if the top elements are negative.

Always take the current maximum

The players alternate turns, each picking the current maximum non-negative element available.

Roy adds the picked value to his score, while Hridoy subtracts it from Roy’s score.

The game continues until no non-negative numbers remain on the board.

Strategy / Final Solution
Step 1: Sort the array in non-increasing order.

Step 2: Alternately let Roy and Hridoy pick the largest remaining value, starting with Roy.

Step 3: Continue this process as long as the picked value is non-negative.

Step 4: If all remaining values are negative, stop the game — but only after both players have taken at least one move.
Time Complexity: O(N log N)

Code (C++) :

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
    	
        int N;
        cin >> N;
        vector<ll> A(N);
        for (int i = 0; i < N; i++) {
            cin >> A[i];
           
        }
        sort(A.rbegin(), A.rend());
        ll sum=0;
        for(int i=0;i<N;i++){
        	if(i>1 && A[i]<=0){
        		break;
        		
        	}
        	if(i%2==0)sum+=A[i];
        	if(i%2==1)sum-=A[i];
        }
        cout<<sum<<"\n";
       
    }

    return 0;
}