```

```

Try fixing the first two elements and generate the sequence using the rule $$$a_i \oplus a_{i+1} = a_{i+2}$$$.

We are given that:

Fix the first two elements $$$a_1 = x$$$ and $$$a_2 = y$$$.

Then:

So the sequence becomes:

Hence, the sequence is periodic with period $$$3$$$.

Therefore: - The array can have only $$$3$$$ distinct values. - These values must be $$$x$$$, $$$y$$$, and $$$x \oplus y$$$.

So, if the number of distinct elements is not $$$3$$$, the answer is $$$\textbf{NO}$$$.

Now let the frequencies of these three values be $$$f_1, f_2, f_3$$$.

Since the sequence repeats every $$$3$$$ positions, the frequencies must be balanced:

If this condition holds, we can arrange elements in cyclic order and the answer is $$$\textbf{YES}$$$, otherwise $$$\textbf{NO}$$$.

$$$\textbf{Complexity}$$$: $$$O(n \log n)$$$ per test case.

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

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

    int t;
    cin >> t;

    while(t--) {
        int n;
        cin >> n;
        map<int,int> mp;
        for(int i = 0; i < n; i++) {
            int x;
            cin >> x;
            mp[x]++;
        }
        
        if(mp.size() != 3){
            cout << "NO\n";
            continue;
        }
        int mx = 0, mn = 1e9;
        for(auto it : mp){
            mx = max(mx, it.second);
            mn = min(mn, it.second);
        }
        
        cout << (mx - mn <= 1 ? "YES\n" : "NO\n");
    }
}

In a binary array, what does a non-decreasing subsequence look like? Try to describe its structure.

Fix a starting index and think in terms of taking some $0$s first and then $1$s. Can you express the length using counts of $0$s and $1$s in a segment?

Try maximizing $$$(\text{number of 0s} - \text{number of 1s})$$$ over a cyclic segment. Can you reduce this to a known problem? \end{itemize}

A non-decreasing subsequence in a binary array must be of the form

Since the array is cyclic, we can choose any starting point and traverse once. This splits the traversal into a segment $$$S$$$ where we take $0$s and the remaining part where we take $1$s.

Let $$$C_1$$$ be the total number of $1$s. Then the length becomes:

But

So:

Thus, we need to maximize $$$(\text{0s} - \text{1s})$$$ over a cyclic segment.

Now map:

Then for any segment, its sum equals $$$(\text{0s} - \text{1s})$$$. So the problem reduces to finding the maximum subarray sum in a circular array.

Using Kadane's algorithm:

Final answer:

Time complexity is $$$O(n)$$$ per test case.

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

void solve() {
    int n;
    cin >> n;

    int totalOnes = 0;
    int totalSum = 0;
    int maxSum = 0, curMax = 0;
    int minSum = 0, curMin = 0;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        if (x == 1) totalOnes++;

        int val = (x == 0 ? 1 : -1);
        totalSum += val;

        curMax = max(val, curMax + val);
        maxSum = max(maxSum, curMax);

        curMin = min(val, curMin + val);
        minSum = min(minSum, curMin);
    }

    int maxCircular = max(maxSum, totalSum - minSum);

    cout << totalOnes + maxCircular << "\n";
}

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

    int t;
    cin >> t;
    while (t--) solve();
}

```

```

```

```

```

```