The Addition Game

Alan works at a company that specialises in computer security. He designed a public key cryptosystem in which the private key is a pair of permutations $\pi$ and $\sigma$ of $\{1, \dots, n\}$. The public key $(a_1, \dots, a_n)$ is then given by $a_i \equiv \pi_i + \sigma_i \pmod n$ for $1 \le i \le n$. The notation $x \equiv y \pmod n$ means that $x$ and $y$ leave the same remainder when divided by $n$.

Take $n = 5$ with

• $\pi = (3, 1, 5, 2, 4)$,
• $\sigma = (5, 1, 3, 4, 2)$.

The public key is then $a = (3, 2, 3, 1, 1)$. For instance $a_5 \equiv 1 \equiv 4 + 2 \equiv \pi_5 + \sigma_5 \pmod 5$, and each of $\pi$ and $\sigma$ contains every number of $\{1, \dots, 5\}$ exactly once.

Alan's coworkers doubt that the system is secure, since any private key matching the public key breaks it. Help them out. Given $n$ and a sequence $a = (a_1, \dots, a_n)$, decide whether there are permutations $\pi$ and $\sigma$ of $\{1, \dots, n\}$ with $\pi_i + \sigma_i \equiv a_i \pmod n$ for every $i$.

The first line contains the length $n$ of the sequence ($1 \le n \le 1000$).

The second line contains $n$ integers $a_1, \dots, a_n$ ($1 \le a_i \le n$).

Print possible if permutations $\pi$ and $\sigma$ with the property above exist, and impossible otherwise.