11220번 - The Addition Game 스페셜 저지다국어

문제

Alan works for a company specialising in computer security. He recently came up with what he thinks is a great public key cryptosystem, in which the private key consists of two permutations π and σ of {1, . . . , n}. The public key (a₁, . . . , a_n) is then given by a_i ≡ π_i + σ_i (mod n) for 1 ≤ i ≤ n. The expression x ≡ y (mod n) means that x and y have the same remainder after division by n.

As an example with n = 5, consider

• π = (3, 1, 5, 2, 4),
• σ = (5, 1, 3, 4, 2), and
• a = (3, 2, 3, 1, 1).

Here, for example, a₅ ≡ 1 ≡ 4 + 2 ≡ π₅ + σ₅ (mod 5), and all the entries in π and σ respectively are {1, . . . , 5}, each number occurring exactly once.

Alan’s coworkers have some doubts about this system being secure, since finding any private key corresponding to the public key would break the system. Your task is to help them out. Given n and a sequence a = (a₁, . . . , a_n), determine whether there are two permutations π and σ such that π_i + σ_i = a_i (mod n) for each i. If there are more such pairs, print any of them.

입력

The first line contains the length n of the sequence and the permutation is written. The second line contains integers a₁, . . . , a_n, satisfying 1 ≤ a_i ≤ n. The length n satisfies 1 ≤ n ≤ 1000.

출력

If there is no solution, output “impossible”. If there is a solution, output any of them, writing the two permutations on one line each.

제한

힌트