[Solution] Circular Local MiniMax Codeforces Solution | Codeforces Problem Solution 2022

[Solution] Circular Local MiniMax Codeforces Solution | Codeforces Problem Solution 2022

C. Circular Local MiniMax

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$. Is it possible to arrange them on a circle so that each number is strictly greater than both its neighbors or strictly smaller than both its neighbors?

In other words, check if there exists a rearrangement b1,b2,…,bn$b_1,b_2,\dots ,b_n$ of the integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ such that for each i$i$ from 1$1$ to n$n$ at least one of the following conditions holds:

• bi−1<bi>bi+1$b_{i-1}<b_i>b_{i+1}$
• bi−1>bi<bi+1$b_{i-1}>b_i<b_{i+1}$

To make sense of the previous formulas for i=1$i=1$ and i=n$i=n$, 

Solution Click Below:-  CLICK HERE

one shall define b0=bn$b_0=b_n$ and bn+1=b1$b_{n+1}=b_1$.

Input

The first line of the input contains a single integer t$t$ (1≤t≤3⋅104$1\le t\le 3\cdot {10}^4$)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer n$n$ (3≤n≤105$3\le n\le {10}^5$)  — the number of integers.

Everything Everywhere All But One Codeforces Solution

Odd Subarrays Codeforces Solution

Circular Local MiniMax Codeforces Solution

Linguistics Codeforces Solution

Bring Balance Codeforces Solution 

Permutation Weight (Easy Version) Codeforces Solution

The second line of each test case contains n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (0≤ai≤109$0\le a_i\le {10}^9$).

The sum of n$n$ over all test cases doesn't exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case, if it is not possible to arrange the numbers on the circle satisfying the conditions from the statement, output NO$\mathtt{\text{NO}}$. You can output each letter in any case.

Otherwise, output YES$\mathtt{\text{YES}}$. In the second line, output n$n$ integers b1,b2,…,bn$b_1,b_2,\dots ,b_n$, which are a rearrangement of a1,a2,…,an$a_1,a_2,\dots ,a_n$ and satisfy the conditions from the statement. If there are multiple valid ways to arrange the numbers, you can output any of them.