Codeforces 892 D. Gluttony （思维）

Codeforces 892 D. Gluttony （思维）

Description

You are given an array a with n distinct integers. Construct an array b by permuting a such that for every non-empty subset of indices S = {x1, x2, …, xk} (1 ≤ xi ≤ n, 0 < k < n) the sums of elements on that positions in a and b are different, i. e. >∑i=1kaxi≠∑i=1kbxi>

Input

The first line contains one integer n (1 ≤ n ≤ 22) — the size of the array.The second line contains n space-separated distinct integers a1, a2, …, an (0 ≤ ai ≤ 10^9) — the elements of the array.

Output

If there is no such array b, print -1.Otherwise in the only line print n space-separated integers b1, b2, …, bn. Note that b must be a permutation of a.If there are multiple answers, print any of them.

Examples input

21 2

Examples output

2 1

题意

寻找给定排列的一个置换，满足任意一个下标集合在 a 与 b 之间选中值的和都不同（不包括全集）。

思路

结论题，首先对原序列进行排序，然后循环左移一位，此时这两个排列满足题目中所说的要求，然后我们把新得到的序列按照原来的下标填入进去即可。

证明：

我们设 t={x1,x2,…,xk} ，a 为排序后的序列， b 为 a

显然，循环左移一位会使得 b1...bn−1>a1...an−1 ，此时关键讨论 n 是否在 t

当 n∉t ，显然 ∀x∈t,bx>ax ，则 ∑ki=1bxi>∑ki=1axi当 n∈t ，我们考虑其逆事件，因为 ∑ni=1ai=∑ni=1bi ，于是 ∑ki=1bxi<∑ki=1axi

因此， ∑ki=1bxi≠∑ki=1axi

AC 代码

#include#define IO ios::sync_with_stdio(false);\ cin.tie(0);\ cout.tie(0);using namespace std;typedef __int64 LL;const int maxn = 1e5+10;int a[maxn];typedef pair P;P p[maxn];int main(){ IO; int n; cin>>n; for(int i=0; i>a[i],p[i] = P(a[i],i); sort(p,p+n); for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。