Problem:


Score : 700 points

Problem Statement

Aoki loves numerical sequences and trees.

One day, Takahashi gave him an integer sequence of length N, a_1, a_2, ..., a_N, which made him want to construct a tree.

Aoki wants to construct a tree with N vertices numbered 1 through N, such that for each i = 1,2,...,N, the distance between vertex i and the farthest vertex from it is a_i, assuming that the length of each edge is 1.

Determine whether such a tree exists.

Constraints

2 ≦ N ≦ 100

1 ≦ a_i ≦ N-1

Input

The input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

If there exists a tree that satisfies the condition, print Possible. Otherwise, print Impossible.

Sample Input 1

5
3 2 2 3 3

Sample Output 1

Possible

The diagram above shows an example of a tree that satisfies the conditions. The red arrows show paths from each vertex to the farthest vertex from it.

Sample Input 2

3
1 1 2

Sample Output 2

Impossible

Sample Input 3

10
1 2 2 2 2 2 2 2 2 2

Sample Output 3

Possible

Sample Input 4

10
1 1 2 2 2 2 2 2 2 2

Sample Output 4

Impossible

Sample Input 5

6
1 1 1 1 1 5

Sample Output 5

Impossible

Sample Input 6

5
4 3 2 3 4

Sample Output 6

Possible



Sample input:
5
3 2 2 3 3


Sample output:
Possible

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
mn,mx = A[0],A[-1]

from collections import Counter
ctr = Counter(A)

if N==2:
    if A==[1,1]:
        print('Possible')
    else:
        print('Impossible')
    exit()
if ctr[mx] < 2:
    print('Impossible')
    exit()
if (mn == 1 and ctr[mn] > 1) or ctr[mn] > 2:
    print('Impossible')
    exit()

for n in range(mn,mx+1):
    if ctr[n]==0:
        print('Impossible')
        exit()
print('Possible')

Submission status: Wrong Answer

Solution code:
import collections
import unittest


def solve(n, a):
    POSSIBLE = 'Possible'
    IMPOSSIBLE = 'Impossible'

    a.sort()
    counter = collections.Counter(a)
    max_k = max(counter)
    min_k = (max_k+1)//2
    if min(counter) < min_k or min_k not in counter:
        return IMPOSSIBLE
    if counter[max_k] < 2:
        return IMPOSSIBLE
    if max_k == 1 and n > 2:
        return IMPOSSIBLE
    if max_k % 2 == 0:
        if counter[min_k] > 1:
            return IMPOSSIBLE
        if any([i not in counter or counter[i] < 2 for i in range(min_k + 1, max_k+1)]):
            return IMPOSSIBLE
    else:
        if any([i not in counter or counter[i] < 2 for i in range(min_k, max_k+1)]):
            return IMPOSSIBLE
    return POSSIBLE


def main():
    n = int(input())
    a = list(map(int, input().split()))
    result = solve(n, a)
    print(result)


if __name__ == "__main__":
    main()


class Test(unittest.TestCase):
    def test1(self):
        n = 5
        a = [3, 2, 2, 3, 3]
        expected = 'Possible'
        self.assertEqual(solve(n, a), expected)

    def test2(self):
        n = 3
        a = [1, 1, 2]
        expected = 'Impossible'
        self.assertEqual(solve(n, a), expected)

    def test3(self):
        n = 10
        a = [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, ]
        expected = 'Possible'
        self.assertEqual(solve(n, a), expected)

    def test4(self):
        n = 10
        a = [1, 1, 2, 2, 2, 2, 2, 2, 2, 2, ]
        expected = 'Impossible'
        self.assertEqual(solve(n, a), expected)

    def test5(self):
        n = 6
        a = [1, 1, 1, 1, 1, 5]
        expected = 'Impossible'
        self.assertEqual(solve(n, a), expected)

    def test6(self):
        n = 5
        a = [4, 3, 2, 3, 4]
        expected = 'Possible'
        self.assertEqual(solve(n, a), expected)

    def test_hand1(self):
        n = 5
        a = [4, 4, 2, 4, 4]
        expected = 'Impossible'
        self.assertEqual(solve(n, a), expected)

    def test_hand2(self):
        n = 2
        a = [1, 1]
        expected = 'Possible'
        self.assertEqual(solve(n, a), expected)

    def test_hand3(self):
        n = 2
        a = [2, 2]
        expected = 'Impossible'
        self.assertEqual(solve(n, a), expected)

    def test_hand4(self):
        n = 3
        a = [1, 1, 1]
        expected = 'Impossible'
        self.assertEqual(solve(n, a), expected)

    def test_hand5(self):
        n = 3
        a = [2, 2, 2]
        expected = 'Impossible'
        self.assertEqual(solve(n, a), expected)

Submission status: Wrong Answer

Solution code:
import collections
import unittest


def solve(n, a):
    POSSIBLE = 'Possible'
    IMPOSSIBLE = 'Impossible'

    a.sort()
    counter = collections.Counter(a)
    max_k = max(counter)
    min_k = (max_k+1)//2
    if min(counter) < min_k or min_k not in counter:
        return IMPOSSIBLE
    if max_k % 2 == 0:
        if counter[min_k] > 1:
            return IMPOSSIBLE
        if any([i not in counter or counter[i] < 2 for i in range(min_k + 1, max_k+1)]):
            return IMPOSSIBLE
    else:
        if any([i not in counter or counter[i] < 2 for i in range(min_k, max_k+1)]):
            return IMPOSSIBLE
    return POSSIBLE


def main():
    n = int(input())
    a = list(map(int, input().split()))
    result = solve(n, a)
    print(result)


if __name__ == "__main__":
    main()


class Test(unittest.TestCase):
    def test1(self):
        n = 5
        a = [3, 2, 2, 3, 3]
        expected = 'Possible'
        self.assertEqual(solve(n, a), expected)

    def test2(self):
        n = 3
        a = [1, 1, 2]
        expected = 'Impossible'
        self.assertEqual(solve(n, a), expected)

    def test3(self):
        n = 10
        a = [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, ]
        expected = 'Possible'
        self.assertEqual(solve(n, a), expected)

    def test4(self):
        n = 10
        a = [1, 1, 2, 2, 2, 2, 2, 2, 2, 2, ]
        expected = 'Impossible'
        self.assertEqual(solve(n, a), expected)

    def test5(self):
        n = 6
        a = [1, 1, 1, 1, 1, 5]
        expected = 'Impossible'
        self.assertEqual(solve(n, a), expected)

    def test6(self):
        n = 5
        a = [4, 3, 2, 3, 4]
        expected = 'Possible'
        self.assertEqual(solve(n, a), expected)

    def test_hand1(self):
        n = 5
        a = [4, 4, 2, 4, 4]
        expected = 'Impossible'
        self.assertEqual(solve(n, a), expected)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
mn,mx = A[0],A[-1]

from collections import Counter
ctr = Counter(A)

if ctr[mx] < 2:
    print('Impossible')
    exit()
if (mn == 1 and ctr[mn] > 1) or ctr[mn] > 2:
    print('Impossible')
    exit()

for n in range(mn,mx+1):
    if ctr[n]==0:
        print('Impossible')
        exit()
print('Possible')

Submission status: Wrong Answer

Solution code:
import collections
import unittest


def solve(n, a):
    POSSIBLE = 'Possible'
    IMPOSSIBLE = 'Impossible'

    a.sort()
    counter = collections.Counter(a)
    max_k = max(counter)
    min_k = (max_k+1)//2
    if min(counter) < min_k or min_k not in counter:
        return IMPOSSIBLE
    if 1 in counter and counter[1] == 2:
        if n == 2:
            return POSSIBLE
        else:
            return IMPOSSIBLE
    if any([i not in counter for i in range(min_k, max_k)]):
        return IMPOSSIBLE
    return POSSIBLE


def main():
    n = int(input())
    a = list(map(int, input().split()))
    result = solve(n, a)
    print(result)


if __name__ == "__main__":
    main()
    # unittest.main()


class Test(unittest.TestCase):
    def test1(self):
        n = 5
        a = [3, 2, 2, 3, 3]
        expected = 'Possible'
        self.assertEqual(solve(n, a), expected)

    def test2(self):
        n = 3
        a = [1, 1, 2]
        expected = 'Impossible'
        self.assertEqual(solve(n, a), expected)

    def test3(self):
        n = 10
        a = [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, ]
        expected = 'Possible'
        self.assertEqual(solve(n, a), expected)

    def test4(self):
        n = 10
        a = [1, 1, 2, 2, 2, 2, 2, 2, 2, 2, ]
        expected = 'Impossible'
        self.assertEqual(solve(n, a), expected)

    def test5(self):
        n = 6
        a = [1, 1, 1, 1, 1, 5]
        expected = 'Impossible'
        self.assertEqual(solve(n, a), expected)

    def test6(self):
        n = 5
        a = [4, 3, 2, 3, 4]
        expected = 'Possible'
        self.assertEqual(solve(n, a), expected)

    def test_hand1(self):
        n = 5
        a = [4, 4, 2, 4, 4]
        expected = 'Impossible'
        self.assertEqual(solve(n, a), expected)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
a.sort()
I,A=min(a),max(a)
c=Counter(a)
p=print
e=exit
if c[A]==1or c[I]>A%2+1or I*2<A:e(p("Impossible"))
for i in range(I+1,A+1):
 if not i in c and c[i]>=2:e(p("Impossible"))
p("Possible")

Submission status: Wrong Answer

Solution code:
from collections import Counter


def main():
    N = int(input())
    A = list(map(int, input().split()))

    C = Counter(A)
    A.sort()
    Amax = A[-1]
    Amin = A[0]

    if Amax == Amin == 1:
        return N == 2
    if Amax % 2 == 0:
        if (Amax // 2) != Amin:
            return False
        if C[Amin] != 1:
            return False
        for a in range(Amin + 1, Amax + 1):
            if C[a] < 2:
                return False
    else:
        if (Amax + 1) // 2 != Amin:
            return False
        for a in range(Amin, Amax + 1):
            if C[a] < 2:
                return False
    return True


if main():
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
from collections import Counter


def main():
    N = int(input())
    A = list(map(int, input().split()))

    C = Counter(A)
    A.sort()
    Amax = A[-1]
    Amin = A[0]

    if Amax % 2 == 0:
        if (Amax // 2) != Amin:
            return False
        if C[Amin] != 1:
            return False
        for a in range(Amin + 1, Amax + 1):
            if C[a] < 2:
                return False
    else:
        if (Amax + 1) // 2 != Amin:
            return False
        for a in range(Amin, Amax + 1):
            if C[a] < 2:
                return False
    return True


if main():
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n = I()
A = LI()
D = Counter(A)
min_a = min(A)
max_a = min_a * 2 if D[min_a] == 1 else min_a * 2 - 1
if D[min_a] > 2:
    print("Impossible")
    exit()
flg = 0
for i in range(min_a + 1, max_a + 1):
    if D[i] < 2:
        print("Impossible")
        exit()
    D[i] -= 2

pre = 0
for i in range(min_a + 1, max_a + 1):
    if D[i] < pre:
        print("Impossible")
        exit()
    pre = D[i]

for k in D.keys():
    if k > max_a:
        print("Impossible")
        exit()

print("Possible")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
class multiset:#同じ要素を複数持てる
    def __init__(self,x=None):#最大値を取り出したいときはクラスの外でマイナスを処理する
        if x==None:
            self.counter=Counter()
            self.q=[]
        else:
            self.counter=Counter(x)
            self.q=list(x)
            heapify(self.q)
    def add(self,a):
        self.counter[a]+=1
        heappush(self.q,a)
    def remove(self,a):
        if self.counter[a]:
            self.counter[a]-=1
            return 1
        else:
            return 0
    def min(self):
        while not self.counter[self.q[0]]:
            heappop(self.q)
        return self.q[0]
    def pop(self):
        while self.q and self.counter[self.q[0]]==0:
            heappop(self.q)
        if self.q:
            self.counter[self.q[0]]-=1
            return heappop(self.q)
        return None
    def __eq__(self,other):
        return other.counter==self.counter
    def __len__(self): return len(self.q)

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    ms=multiset(A)
    ma=max(A)
    for i in range(ma+1):
        t=max(i,ma-i)
        f=ms.remove(t)
        if not f:
            print("Imporssible")
            return
    
    sles=math.ceil(ma*0.5)+1
    while True:
        x=ms.pop()
        if x==None:
            break

        if x>=sles:
            continue
        else:
            print("Impossible")
            return
    print("Possible")
    




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = [int(x) for x in input().split()]

c = Counter()
for x in a:
    c[x] += 1

m = max(a)
for i in range(m//2+1, m+1):
    if c[i] < 1:
        print("Impossible")
        exit()

if m % 2 == 1 and c[m//2+1] != 2:
    print("Impossible")
elif m % 2 == 0 and c[m//2] != 1:
    print("Impossible")
else:
    print("Possible")

Submission status: Wrong Answer

Solution code:
from sys import stdin
input = stdin.readline
n = int(input())
aa = list(map(int, input().split()))
print("Possible")

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
a=list(map(int,input().split()))
a.sort()
maxlen=a[-1]
thing={}
for i in range(n):
  if a[i] in thing:
    thing[a[i]]+=1
  else:
    thing[a[i]]=1
    
if maxlen%2==1:
  if not (maxlen+1)//2 in thing:
    print('Impossible')
    sys.exit()
  if thing[(maxlen+1)//2]!=2:
    print('Impossible')
    sys.exit()
if maxlen%2==0:
  if not (maxlen+1)//2 in thing:
    print('Impossible')
    sys.exit()
  if thing[(maxlen+1)//2]!=1:
    print('Impossible')
    sys.exit()
for i in thing:
  if i==(maxlen+1)//2:
    continue
  if i<(maxlen+1)//2:
    print('Impossible')
    sys.exit()
  if thing[i]<2:
    print('Impossible')
    sys.exit()
print('Possible')

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
a=list(map(int,input().split()))
a.sort()
maxlen=a[-1]
thing={}
for i in range(n):
  if a[i] in thing:
    thing[a[i]]+=1
  else:
    thing[a[i]]=1
if maxlen%2==1:
  if not (maxlen+1)//2 in thing:
    print('Impossible')
    sys.exit()
  if thing[(maxlen+1)//2]!=2:
    print('Impossible')
    sys.exit()
if maxlen%2==0:
  if not (maxlen+1)//2 in thing:
    print('Impossible')
    sys.exit()
  if thing[(maxlen+1)//2]!=1:
    print('Impossible')
    sys.exit()
for i in thing:
  if i<(maxlen+1)//2:
    print('Impossible')
    sys.exit()
  if thing[i]<2:
    print('Impossible')
    sys.exit()
print('Possible')

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

A = np.array(read().split(), np.int32)[1:]

def f(A):
    diam = A.max()
    if np.any(2*A < diam):
        return False
    count = np.bincount(A)
    if diam & 1:
        return np.all(count[(diam+1)//2:] >= 2)
    if count[diam//2] != 1:
        return False
    return np.all(count[diam//2+1:] >= 2)

print('Possible' if f(A) else 'Impossible')

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    a.sort(reverse=True)
    res = []
    k = a[0]
    if a[-1] < k//2:
        print("Impossible")
        exit()
    d = defaultdict(int)
    for i in a:
        d[i] += 1
    if k&1:
        if d[k//2+1] != 2:
            print("Impossoble")
            exit()
        for i in range(k//2+2,k+1):
            if d[i] < 2:
                print("Impossoble")
                exit()
    else:
        if d[k//2] != 1:
            print("Impossible")
            exit()
        for i in range(k//2+1,k+1):
            if d[i] < 2:
                print("Impossoble")
                exit()
    print("Possoble")



    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
x = sorted(set(a))
if (max(a) - 1) // 2 + 1 == min(a):
  if max(a) & 1:
    m = 0
    for i in range(x[0],x[-1]+1):
      if a.count(i) < 2: m = 1
    if m:
      print("Impossible")
    else:
      print("Possible")
  else:
    m = a.count(x[0]) != 1
    for i in range(x[0]+1,x[-1]+1):
      if a.count(i) < 2: m = 1
    if m:
      print("Impossible")
    else:
      print("Possible")
else:
  print("Impossible")

Submission status: Wrong Answer

Solution code:
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
n=N()
l=L()
l.sort()
def im():
    print("Impossible")
    quit()
def po():
    print("Possible")
    quit()
if l[0]!=(l[-1]+1)//2:
    im()
import collections
c=collections.Counter(l)
if l[-1]%2:
    for i in range((l[-1]+1)//2,l[-1]+1):
        if c[i]<2:
            im()
    po()
if c[l[0]]!=1:
    im()
for i in range(l[0]+1,l[-1]+1):
    if c[i]<2:
        im()
po()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
a.sort()
m, n = max(a), min(a)
if n * 2 == m:
    cnt = [0] * (m - n + 1)
    for i in range(N):
        cnt[a[i] - n] += 1
    if cnt[0] == 1 and all(c >= 2 for c in cnt[1:]):
        print('Possible')
    else:
        print('Impossible')
elif n * 2 - 1 == m:
    cnt = [0] * (m - n + 1)
    for i in range(N):
        cnt[a[i] - n] += 1
    if all(c >= 2 for c in cnt):
        print('Possible')
    else:
        print('Impossible')
else:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
a.sort()
if a[0] * 2 == a[-1]:
    for i in range(1, N-1):
        if a[i-1] != a[i] and a[i] != a[i+1]:
            print('Impossible')
            exit()
    if a[0] == a[1] or a[-2] != a[-1]:
        print('Impossible')
    else:
        print('Possible')
elif a[0] * 2 - 1 == a[-1]:
    for i in range(1 , N-1):
        if a[i-1] != a[i] and a[i] != a[i+1]:
            print('Impossible')
            exit()
    if a[0] != a[1] or a[-2] != a[-1]:
        print('Impossible')
    else:
        print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
N,*A = map(int, open(0).read().split())
Cnt = Counter(A)
if Cnt[1]>1:
  if N==2:
    print('Possible')
  else:   
    print('Impossible')
  sys.exit()
m = max(A)
S = set()
for i in range(m):
  S.add(max(m-1-i,i+1))
for a in A:
  if a not in S:
    print('Impossible')
    sys.exit()
for c in S:
  if Cnt[c]==0:
    print('Impossible')
    sys.exit()
print('Possible')

Submission status: Wrong Answer

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################


n = int(input())
a = list(map(int, input().split()))

num = Zeros(n,-1)

for i in range(n):
    num[a[i]] += 1

mx = max(a)
    
#print(num)
ans = "Possible"
if(mx%2==0):
    num[mx//2] -= 1
    if(num[mx//2]<0): ans="Impossible"

now = mx//2 + 1


for i in range(mx-now+1):
    num[now+i]-=2
    if(num[now+i]<0): ans="Impossible"
#print(num)

if(sum(num[0:now])>=1):
    ans = "Impossible"

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=1)
if a[0]!=a[1]:
  print("Impossible")
  exit()
m=[0]*n
for i in range(1,a[0]):m[max(i,a[0]-i)]+=1
for i in a:m[i]-=1
for i in m:
  if i>0:print("Impossible");exit()
if m[0--a[0]//2]!=0:print("Impossible");exit()
print("Possible")

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=1)
if a[0]!=a[1]:
  print("Impossible")
  exit()
m=[0]*n
for i in range(1,a[0]):m[max(i,a[0]-i)]+=1
for i in a:m[i]-=1
for i in m:
  if i>0:print("Impossible");exit()
if m[a[0]//2]!=0:print("Impossible");exit()
print("Possible")

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=1)
if a[0]!=a[1]:
  print("Impossible")
  exit()
m=[0]*n
for i in range(1,a[0]):m[max(i,a[0]-i)]+=1
for i in a:m[i]-=1
for i in m:
  if i>0:print("Impossible");exit()
if a[0]%2==0:
  if m[a[0]//2]!=0:print("Impossible");exit()
print("Possible")

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))

def canMake():
    if N == 2:
        return A == [1, 1]

    cntA = Counter(A)
    mi = min(A)
    mx = max(A)

    if sum([c < 2 for c in cntA.values()]) >= 2:
        return False
    if cntA[mi] >= 2:
        return False

    for i in range(mi, mx + 1):
        if cntA[i] == 0:
            return False

    return True

print('Possible' if canMake() else 'Impossible')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
a.sort()
d = [[10 ** 6 for _ in range(N)] for _ in range(N)]
#print(a)

if N == 2:
  if a != [1, 1]:
    print("Impossible")
    exit(0)
else:
  if max(a) < 2:
    print("Impossible")
    exit(0)

mn = min(a)
mnl = []
for i in range(N):
  if a[i] == mn: mnl.append(i)
for i in range(len(mnl)):
  for j in range(len(mnl)): d[i][j] = 1

for x in range(min(a), max(a)):
  l = []
  r = []
  for i in range(N):
    if a[i] == x: l.append(i)
  for i in range(N):
    if a[i] == x + 1: r.append(i)
  if len(l) == 0:
    print("Impossible")
    exit(0)
  for i in range(len(r)):
    y = l[i % len(l)]
    z = r[i]
    d[y][z] = 1
    d[z][y] = 1

for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j] = min(d[i][k] + d[k][j], d[i][j])

#print(d)
for i in range(N):
  if a[i] != max(d[i]):
    print("Impossible")
    exit(0)
print("Possible")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
a.sort()
d = [[10 ** 6 for _ in range(N)] for _ in range(N)]
#print(a)
mn = min(a)
mnl = []
for i in range(N):
  if a[i] == mn: mnl.append(i)
for i in range(len(mnl)):
  for j in range(len(mnl)): d[i][j] = 1

for x in range(min(a), max(a)):
  l = []
  r = []
  for i in range(N):
    if a[i] == x: l.append(i)
  for i in range(N):
    if a[i] == x + 1: r.append(i)
  if len(l) == 0:
    print("Impossible")
    exit(0)
  for i in range(len(r)):
    y = l[i % len(l)]
    z = r[i]
    d[y][z] = 1
    d[z][y] = 1

for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j] = min(d[i][k] + d[k][j], d[i][j])

#print(d)
for i in range(N):
  if a[i] != max(d[i]):
    print("Impossible")
    exit(0)
print("Possible")

Submission status: Wrong Answer

Solution code:
_,a=open(0)
*a,=map(int,a.split())
m=max(a)
c=[0]*-~m
for i in a:c[i]+=1
print(sum(c[:-~m//2])<1and~m%2==c[m//2]and all(c[i+1]>1for i in range(m//2,m))and'Possible'or'Impossible')

Submission status: Wrong Answer

Solution code:
_,a=open(0)
*a,=map(int,a.split())
m=max(a)
c=[0]*-~m
for i in a:c[i]+=1
print(sum(c[:m//2])<1and~m%2==c[m//2]and all(c[i+1]>1for i in range(m//2,m))and'Possible'or'Impossible')

Submission status: Wrong Answer

Solution code:
N=int(input())
L=list(map(int,input().split()))
D={}
for i in range(N):
    if L[i] not in D:
        D[L[i]]=1
    else:
        D[L[i]]+=1
L=list(D.items())
L.sort()
#print(L)

if L[-1][1]<=1:
    print("Impossible")
    exit()
if L[-1][0]%2==1:
    if L[-1][0]//2+1==L[0][0] and L[0][1]==2:
        print("Possible")
    else:
        print("Impossible")
else:
    if L[-1][0]//2==L[0][0] and L[0][1]==1:
        print("Possible")
    else:
        print("Impossible")

Submission status: Wrong Answer

Solution code:
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
x=max(a)
c=Counter(a)
flg=1
for i in range((x+1)//2,x+1):
  if i == (x+1)//2:
    if x%2==0:
      if c[i]==0:
        flg=0
    else:
      if c[i]<=1:
        flg=0
  else:
    if c[i]<=1:
      flg=0
if flg:
  print("Possible")
else:
  print("Impossible")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

C = sorted(Counter(A).items())
M = len(C)

if C[0][1] > 2:
    print('Impossible')
    exit()

is2src = C[0][1] == 2
src = C[0][0]
depth = src - is2src + 1

if not is2src and C[1][1] < 2:
    print('Impossible')
    exit()

if len(C) != depth:
    print('Impossible')
    exit()

for i, (k, v) in enumerate(C[1:], 1):
    prevk, prevv = C[i-1]
    if k != prevk + 1:
        print('Impossible')
        exit()
    if prevv > v:
        print('Impossible')
        exit()
print('Possible')

Submission status: Wrong Answer

Solution code:
from collections import Counter

N, *A = map(int, open(0).read().split())

C = Counter(A)
ma = max(C)
mi = min(C)

if (ma == 2 * mi and C[ma] >= 2 and C[mi] == 1) or \
    (ma == 2 * mi - 1 and C[ma] >= 2 and C[mi] == 2) and \
    all(C[i] >= 2 for i in range(mi + 1, ma)):
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
from collections import Counter as C
n=int(input())
a=sorted(C(list(map(int,input().split()))).items())
d=0
if a[-1][0]%2==0:
    d=1
q=1
for i in range(len(a)-1,-1,-1):
    if d:
        if a[i][0]==a[-1][0]//2:
            if a[i][1]!=1:
                q=0
                break
        elif a[i][0]<a[-1][0]//2:
            q=0
            break
        elif a[i][0]!=a[-1][0]+i-len(a)+1:
            q=0
            break
        elif a[i][1]<2 and i!=0:
            q=0
            break
    else:
        if a[i][0]<=a[-1][0]//2:
            q=0
            break
        elif a[i][0]!=a[-1][0]+i-len(a)+1:
            q=0
            break
        elif a[i][1]<2:
            q=0
            break
if q:
    print("Possible")
else:
    print("Impossible")