Circular Local MiniMax

题意翻译

## 题目描述 给你 $n$ 个整数 $ a_1, a_2, \ldots, a_n $ 。 问有没有可能将它们排列在一个圆上，使每个数字严格地大于其相邻的两个数字或严格地小于其相邻的两个数字？ 换句话说，检查是否存在 $ b_1, b_2, \ldots, b_n $ 的整数 $ a_1, a_2, \ldots, a_n $ 的重新排列，使得 $ i $ 从 $ 1 $ 到 $ n $ 中至少有一个以下条件成立。 - $ b_{i-1} < b_i > b_{i+1} $ - $ b_{i-1} > b_i < b_{i+1} $ 为了使前面的公式对 $ i=1 $ 和 $ i=n $ 有意义，我们应定义 $ b_0=b_n $ 和 $ b_{n+1}=b_1 $。 ## 输入格式： 输入的第一行包含一个整数 $ t $ ( $ 1 \le t \le 3\cdot 10^4 $ ) ，表示数据组数。 接下来 $T$ 行，第一行包含一个的整数 $ n $ ( $ 3 \le n \le 10^5 $ ) ， 第二行包含 $ n $ 整数 $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 10^9 $ ) 。（$\sum n \le 2 \cdot 10^5$） ## 输出格式 对于每组数据，如果不可能将数字排列在满足语句条件的圆圈上，则输出 $ \texttt{NO} $ 。 否则，输出 $ \texttt{YES} $ 。在第二行，输出 $ b_1, b_2, \ldots, b_n $ ，这是 $ a_1, a_2, \ldots, a_n $ 的重新排列，并且满足声明中的条件。如果有多种有效的数字排列方式，你可以输出其中任何一种。 ## 样例解释 可以证明，对于第一个和第三个测试案例，没有有效的安排。 在第二个测试案例中，安排 $ [1, 8, 4, 9] $ 是有效的。在这个排列中，$1$ 和 $4$ 都比它们相邻的数小，而 $8、9$ 则较大。 在第四个测试案例中，排列方式 $[1，11，1，111，1，1111]$ 有效。在这个排列中，等于$1$的三个元素比它们相邻的数小，而所有其他元素都比它们相邻的数大。

题目描述

You are given $ n $ integers $ a_1, a_2, \ldots, 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 $ b_1, b_2, \ldots, b_n $ of the integers $ a_1, a_2, \ldots, a_n $ such that for each $ i $ from $ 1 $ to $ n $ at least one of the following conditions holds: - $ b_{i-1} < b_i > b_{i+1} $ - $ b_{i-1} > b_i < b_{i+1} $ To make sense of the previous formulas for $ i=1 $ and $ i=n $ , one shall define $ b_0=b_n $ and $ b_{n+1}=b_1 $ .

输入输出格式

输入格式

The first line of the input contains a single integer $ t $ ( $ 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 $ ( $ 3 \le n \le 10^5 $ ) — the number of integers. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 10^9 $ ). The sum of $ n $ over all test cases doesn't exceed $ 2\cdot 10^5 $ .

输出格式

For each test case, if it is not possible to arrange the numbers on the circle satisfying the conditions from the statement, output $ \texttt{NO} $ . You can output each letter in any case. Otherwise, output $ \texttt{YES} $ . In the second line, output $ n $ integers $ b_1, b_2, \ldots, b_n $ , which are a rearrangement of $ a_1, a_2, \ldots, 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.

输入输出样例

输入样例 #1

4
3
1 1 2
4
1 9 8 4
4
2 0 2 2
6
1 1 1 11 111 1111

输出样例 #1

NO
YES
1 8 4 9 
NO
YES
1 11 1 111 1 1111

说明

It can be shown that there are no valid arrangements for the first and the third test cases. 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.

题目大意：
给定n个整数\(a_1, a_2, \ldots, a_n\)，问是否可能将它们排列在一个圆上，使得每个数字严格地大于其相邻的两个数字或严格地小于其相邻的两个数字。换句话说，是否存在\(a_1, a_2, \ldots, a_n\)的重新排列\(b_1, b_2, \ldots, b_n\)，使得对于每个\(i\)从1到\(n\)，至少满足以下一个条件：
- \(b_{i-1} < b_i > b_{i+1}\)
- \(b_{i-1} > b_i < b_{i+1}\)
为了使前面的公式对\(i=1\)和\(i=n\)有意义，我们定义\(b_0=b_n\)和\(b_{n+1}=b_1\)。

输入格式：
输入的第一行包含一个整数\(t\)（\(1 \le t \le 3 \cdot 10^4\)），表示数据组数。
接下来有\(t\)组数据，每组数据有两行，第一行包含一个整数\(n\)（\(3 \le n \le 10^5\)），第二行包含\(n\)个整数\(a_1, a_2, \ldots, a_n\)（\(0 \le a_i \le 10^9\)）。（\(\sum n \le 2 \cdot 10^5\)）

输出格式：
对于每组数据，如果不可能将数字排列在满足语句条件的圆圈上，则输出\(\texttt{NO}\)。
否则，输出\(\texttt{YES}\)。在第二行，输出\(b_1, b_2, \ldots, b_n\)，这是\(a_1, a_2, \ldots, a_n\)的重新排列，并且满足声明中的条件。如果有多种有效的数字排列方式，你可以输出其中任何一种。题目大意： 给定n个整数\(a_1, a_2, \ldots, a_n\)，问是否可能将它们排列在一个圆上，使得每个数字严格地大于其相邻的两个数字或严格地小于其相邻的两个数字。换句话说，是否存在\(a_1, a_2, \ldots, a_n\)的重新排列\(b_1, b_2, \ldots, b_n\)，使得对于每个\(i\)从1到\(n\)，至少满足以下一个条件： - \(b_{i-1} < b_i > b_{i+1}\) - \(b_{i-1} > b_i < b_{i+1}\) 为了使前面的公式对\(i=1\)和\(i=n\)有意义，我们定义\(b_0=b_n\)和\(b_{n+1}=b_1\)。 输入格式： 输入的第一行包含一个整数\(t\)（\(1 \le t \le 3 \cdot 10^4\)），表示数据组数。 接下来有\(t\)组数据，每组数据有两行，第一行包含一个整数\(n\)（\(3 \le n \le 10^5\)），第二行包含\(n\)个整数\(a_1, a_2, \ldots, a_n\)（\(0 \le a_i \le 10^9\)）。（\(\sum n \le 2 \cdot 10^5\)） 输出格式： 对于每组数据，如果不可能将数字排列在满足语句条件的圆圈上，则输出\(\texttt{NO}\)。 否则，输出\(\texttt{YES}\)。在第二行，输出\(b_1, b_2, \ldots, b_n\)，这是\(a_1, a_2, \ldots, a_n\)的重新排列，并且满足声明中的条件。如果有多种有效的数字排列方式，你可以输出其中任何一种。