덧셈 게임

앨런은 컴퓨터 보안 회사에서 일한다. 그가 만든 공개키 암호에서 개인키는 $\{1, \dots, n\}$의 순열 $\pi$와 $\sigma$ 두 개다. 공개키 $(a_1, \dots, a_n)$은 $1 \le i \le n$에 대해 $a_i \equiv \pi_i + \sigma_i \pmod n$으로 정해진다. $x \equiv y \pmod n$은 $x$와 $y$를 $n$으로 나눈 나머지가 같다는 뜻이다.

$n = 5$이고

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

인 경우를 보자. 공개키는 $a = (3, 2, 3, 1, 1)$이 된다. 예를 들어 $a_5 \equiv 1 \equiv 4 + 2 \equiv \pi_5 + \sigma_5 \pmod 5$이고, $\pi$와 $\sigma$에는 $1$부터 $5$까지가 각각 정확히 한 번씩 들어 있다.

동료들은 이 암호가 안전한지 의심한다. 공개키에 맞는 개인키를 하나라도 찾으면 암호가 뚫리기 때문이다. $n$과 수열 $a = (a_1, \dots, a_n)$이 주어질 때, 모든 $i$에 대해 $\pi_i + \sigma_i \equiv a_i \pmod n$을 만족하는 $\{1, \dots, n\}$의 순열 $\pi$와 $\sigma$가 존재하는지 판정하라.

첫째 줄에 수열의 길이 $n$이 주어진다 ($1 \le n \le 1000$).

둘째 줄에 정수 $a_1, \dots, a_n$이 주어진다 ($1 \le a_i \le n$).

조건을 만족하는 순열 $\pi$와 $\sigma$가 존재하면 possible을, 존재하지 않으면 impossible을 출력한다.