A_Circular_Local_MiniMax.cpp

#include <bits/stdc++.h>
#include <algorithm>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#define pb push_back
#define nl '\n'
#define sp ' '
#define pi 2 * acos(0.0)
#define mod 1000000007

// Types of declarations /////////////////////////////////
#define all(x) x.begin(), x.end()
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;

// Odd Even /////////////////////////////////////////////
bool odd(ll num) { return ((num & 1) == 1); }
bool even(ll num) { return ((num & 1) == 0); }

//////////////////////////////////////////////////////// Prime

bool isPrime(int n)
{
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

///////////////////////////////////////////////////////// LCM GCD
long long gcd(long long a, long long b)
{
    while (b != 0)
    {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

long long lcm(long long a, long long b)
{
    return (a / gcd(a, b)) * b;
}
////////////////////////////////////////////////////////// SQR ROOT

long long sqrt(long long x)
{
    long long s = 0, e = 2e9, res = s;
    while (s <= e)
    {
        long long m = (s + e) / 2;
        if (m * m <= x)
            res = m, s = m + 1;
        else
            e = m - 1;
    }
    return res;
}
////////////////////////////////////////////////////////// BINOMIAL COEFF
vl fact(2e5 + 5, 1);
ll binPow(ll a, ll b)
{
    if (b == 0)
        return 1;
    if (b == 1)
        return a;
    ll ret = binPow(a, b / 2);
    if (b % 2 == 0)
        return (ret * ret) % mod;
    return ((ret * ret) % mod * a) % mod;
}
ll inv(ll a)
{
    return (binPow(a, mod - 2) % mod + mod) % mod;
}
ll binom(ll a, ll b)
{
    if (b < 0 or a < 0)
        return 0;
    return (((fact[a] * inv(fact[b])) % mod * inv(fact[a - b])) % mod + mod) % mod;
}

/*
    vi a(n);
    for(int i=0; i<n; i++){
        cin>>a[i];
    }
*/
#define cno cout << "NO\n"
#define cyes cout << "YES\n"
/*----------------------------------------------------------------------------*/

/*
PROBLEM UNDERSTANDING:
- We need to arrange n numbers in a circle
- Each number must be either a local maximum OR local minimum
- Local maximum: greater than both neighbors
- Local minimum: smaller than both neighbors
- Since it's circular: first element's neighbors are last and second element

KEY OBSERVATIONS:
1. If n is odd, it's impossible because in a circle, we alternate max-min-max-min...
   But with odd numbers, we can't have perfect alternation
2. If n is even, we can try to alternate small-large-small-large...
3. We need exactly n/2 minimums and n/2 maximums
*/

void solve()
{
    int n;
    cin >> n;
    int low = 0, high = n / 2; // Two pointers for smallest and largest halves
    vector<int> vec(n), arr;
    for (auto &i : vec)
    {
        cin >> i;
    }

    // Sort to separate into smallest n/2 and largest n/2 elements
    sort(vec.begin(), vec.end());

    // If n is odd, impossible to create alternating pattern in circle
    if (n % 2 == 1)
    {
        cno;
        return;
    }

    // CONSTRUCTION STRATEGY:
    // - Use smallest n/2 elements as local minimums
    // - Use largest n/2 elements as local maximums
    // - Alternate between them: small, large, small, large...

    bool flag = true; // true = pick from small half, false = pick from large half
    while (high < n)
    {
        if (flag)
        {
            arr.pb(vec[low]); // Add from smallest half (will be local minimum)
            low++;
        }
        else
        {
            arr.pb(vec[high]); // Add from largest half (will be local maximum)
            high++;
        }
        flag = !flag; // Alternate between small and large
    }

    // VERIFICATION: Check if our arrangement satisfies the conditions
    // Each element must be either local max OR local min

    flag = true; // Will track if arrangement is valid

    // Check all middle elements (not first or last)
    for (int i = 1; i < n - 1; i++)
    {
        // Element i must be either:
        // 1. Local maximum: arr[i] > arr[i-1] AND arr[i] > arr[i+1]
        // 2. Local minimum: arr[i] < arr[i-1] AND arr[i] < arr[i+1]
        if ((arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) ||
            (arr[i] < arr[i - 1] && arr[i] < arr[i + 1]))
        {
            continue; // This element satisfies the condition
        }
        else
        {
            flag = false; // Invalid arrangement
        }
    }

    // Check first element (index 0) - its neighbors are last element and second element
    if (!((arr[0] > arr[n - 1] && arr[0] > arr[1]) ||
          (arr[0] < arr[n - 1] && arr[0] < arr[1])))
    {
        flag = false;
    }

    // Check last element (index n-1) - its neighbors are second-to-last and first element
    if (!((arr[n - 1] > arr[n - 2] && arr[n - 1] > arr[0]) ||
          (arr[n - 1] < arr[n - 2] && arr[n - 1] < arr[0])))
    {
        flag = false;
    }

    // Output result
    if (flag)
    {
        cyes;
        for (auto &i : arr)
        {
            cout << i << sp;
        }
        cout << endl;
    }
    else
    {
        cno;
        return;
    }
}

/*
ALGORITHM SUMMARY:
1. Sort the array to get smallest and largest halves
2. If n is odd, return NO (impossible)
3. Alternate picking from smallest half and largest half
4. Verify that each element is either local max or local min
5. Handle circular nature by checking first and last elements specially

TIME COMPLEXITY: O(n log n) due to sorting
SPACE COMPLEXITY: O(n) for the arrangement array

EXAMPLE: [1, 9, 8, 4]
- After sorting: [1, 4, 8, 9]
- Small half: [1, 4], Large half: [8, 9]
- Alternating: 1(small), 8(large), 4(small), 9(large)
- Result: [1, 8, 4, 9]
- Verification: 1<8>4<9 (alternating local min/max) ✓
*/

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

    int t = 1;
    cin >> t;
    while (t--)
        solve();
}
In the second test case, the arrangement[1, 8, 4, 9] works.In this arrangement, 1 and 4 are both smaller than their neighbors, and 8, 9 are larger.

                                                                                                                                      In the fourth test case,
    the arrangement[1, 11, 1, 111, 1, 1111] works.In this arrangement, the three elements equal to 1 are smaller than their neighbors, while all other elements are larger than their neighbors.

                                                                                                                                               * /

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

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