2019-2020 ICPC, Asia Jakarta Regional Contest A. Copying Homework

Danang and Darto are classmates. They are given homework to create a permutation of N integers from 1 to N. Danang has completed the homework and created a permutation A of N integers. Darto wants to copy Danang's homework, but Danang asks Darto to change it up a bit so it does not look obvious that Darto copied.

The difference of two permutations of N integers A and B, denoted by diff(A,B), is the sum of the absolute difference of Ai and Bi for all i. In other words, diff(A,B)=ΣNi=1|Ai−Bi|. Darto would like to create a permutation of N integers that maximizes its difference with A. Formally, he wants to find a permutation of N integers Bmax such that diff(A,Bmax)≥diff(A,B′) for all permutation of N integers B′.

Darto needs your help! Since the teacher giving the homework is lenient, any permutation of N integers B is considered different with A if the difference of A and B is at least N. Therefore, you are allowed to return any permutation of N integers B such that diff(A,B)≥N.

Of course, you can still return Bmax if you want, since it can be proven that diff(A,Bmax)≥N for any permutation A and N>1. This also proves that there exists a solution for any permutation of N integers A. If there is more than one valid solution, you can output any of them.

Input

Input begins with a line containing an integer: N (2≤N≤100000) representing the size of Danang's permutation. The next line contains N integers: Ai (1≤Ai≤N) representing Danang's permutation. It is guaranteed that all elements in A are distinct.

Output

Output in a line N integers (each separated by a single space) representing the permutation of N integers B such that diff(A,B)≥N. As a reminder, all elements in the permutation must be between 1 to N and distinct.

Examples

input

4
1 3 2 4
output

4 2 3 1
input

2
2 1
output

1 2
Note

Explanation for the sample input/output #1

With A=[1,3,2,4] and B=[4,2,3,1], diff(A,B)=|1−4|+|3−2|+|2−3|+|4−1|=3+1+1+3=8. Since 8≥4, [4,2,3,1] is one of the valid output for this sample.

解题思路j：题目要求的是将数组元素重新排列，使得对应位置上的元素相减和的绝对值最大，即保证最大程度每一位上的元素都不同，将第一位对应最后一位，第二位对应倒数第二位，...。

AC代码：

#include <iostream>

using namespace std;

int main()

{

    int n,a;

    while(cin>>n)

    {

        for(int i=;i<=n;i++)

        {

            cin>>a;

            cout<<n-a+<<" ";

        }

        cout<<endl;

    }

    return ;

}

巴特西

2019-2020 ICPC, Asia Jakarta Regional Contest A. Copying Homework

最新文章

热门文章