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

Solution (Python):
from collections import Counter
def solve(A):
    m = min(A)
    cnt = Counter(A)

    if cnt[m] > 2:
        return False

    if cnt[m] == 2:
        d = m-1
    else:
        d = m

    if max(A) > d+m:
        return False

    for i in range(1,d+1):
        if cnt[i+m] < 2:
            return False


    return True




if __name__ == '__main__':
    N = int(input())
    A = list(map(int,input().split()))
    print('Possible' if solve(A) else 'Impossible')

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
m = min(a)
M = max(a)
from collections import Counter
c = Counter(a)
ans = True
if c[m]==1:
    if 2*m<M:
        ans = False
elif c[m]==2:
    if 2*m-1<M:
        ans = False
else:
    ans = False
if ans:
    for i in range(m+1, M+1):
        if i not in c or c[i]<=1:
            ans = False
            break
if ans:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
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 (mx%2==0 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')

Solution (Python):
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 counter[min_k] != 2:
            return IMPOSSIBLE
        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)

    def test_hand6(self):
        n = 95
        a = [22, 23, 25, 20, 22, 16, 21, 22, 14, 25, 14, 16, 20, 21, 17, 18, 21, 14, 23, 23, 15, 19, 15, 17, 22, 24, 22, 23, 15, 25, 13, 21, 24, 15, 23, 15, 15, 24, 21, 15, 25, 16, 21, 16, 25, 19, 21,
             15, 18, 21, 19, 13, 17, 20, 16, 19, 15, 23, 24, 21, 20, 25, 25, 16, 22, 21, 14, 24, 16, 16, 16, 17, 14, 24, 18, 13, 22, 20, 25, 17, 14, 14, 20, 14, 14, 15, 14, 14, 23, 18, 24, 14, 14, 25, 25]
        expected = 'Impossible'
        self.assertEqual(solve(n, a), expected)

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

Solution (Python):
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter



input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def pim():
    print("Impossible")
    sys.exit()
def pp():
    print("Possible")
    sys.exit()
def solve():
    n = getN()
    nums = getList()
    cnt = Counter(nums)
    mx = max(nums)
    mn = min(nums)

    if cnt[mx] < 2:
        pim()
    if mn < (mx + 1) // 2:
        pim()

    if mx % 2 == 0:
        if cnt[mx//2] != 1:
            pim()
    else:
        if cnt[(mx+1) // 2] != 2:
            pim()

    for i in range((mx + 1) // 2 + 1, mx+1):
        if cnt[i] < 2:
            pim()

    pp()


def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    
    solve()

Solution (Python):
from collections import Counter

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

count_A = Counter(As)
max_A = max(As)
min_A = min(As)

ans = False
if max_A % 2 == 0:
    if max_A // 2 == min_A and count_A[min_A] == 1:
        for A in range(min_A + 1, max_A + 1):
            if count_A[A] < 2:
                break
        else:
            ans = True
else:
    if max_A // 2 + 1 == min_A and count_A[min_A] == 2:
        for A in range(min_A + 1, max_A + 1):
            if count_A[A] < 2:
                break
        else:
            ans = True

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

Solution (Python):
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")

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
if n==1:
    if a[0]==1 and a[1]==1:
        print('Possible')
    else:
        print('Impossible')
    exit()
a.sort()
mxa=max(a)
mia=min(a)
from collections import Counter
ca=Counter(a)
if ca[mxa]==1:
    print('Impossible')
    exit()
if ca[mia]>1+mxa%2:
    print('Impossible')
    exit()
if 2*mia<mxa:
    print('Impossible')
    exit()
for i in range(mia+1,mxa+1):
    if i in ca and ca[i]>=2:
        pass
    else:
        print('Impossible')
        exit()
print('Possible')

Solution (Python):
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
        if C[Amin] != 2:
            return False
        for a in range(Amin + 1, Amax + 1):
            if C[a] < 2:
                return False
    return True


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

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

d = max(a)
for i in range(d+1):
    num = max(d-i, i)
    if num in a:
        a.remove(num)
    else:
        print('Impossible')
        exit()

if a == []:
    print('Possible')
    exit()
mini = min(a)
if mini >= (d+1)//2 + 1:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
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 or max(A) > max_a:
    print("Impossible")
    exit()

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

print("Possible")

Solution (Python):
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

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

print("Possible")

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
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

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import reduce,lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
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
    

    N = int(input())
    
    A = tuple(map(int, input().split())) 
    
    
    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("Impossible")
            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()

Solution (Python):
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)
chk = True
if m % 2:
    for i in range(1, m+1):
        if i < m//2+1 and c[i] > 0:
            chk = False
        elif i == m//2+1 and c[i] != 2:
            chk = False
        elif i > m//2+1 and c[i] < 2:
            chk = False
else:
    for i in range(1, m+1):
        if i < m//2 and c[i] > 0:
            chk = False
        elif i == m//2 and c[i] != 1:
            chk = False
        elif i > m//2 and c[i] < 2:
            chk = False

print("Possible" if chk else "Impossible")

Solution (Python):
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()
for i in range((maxlen+1)//2,maxlen):
  if not i in thing:
    print('Impossible')
    sys.exit()
print('Possible')

Solution (Python):
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:
        if count[(diam + 1) // 2] != 2:
            return False
        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')

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


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]
    d = defaultdict(int)
    for i in a:
        d[i] += 1
    if k&1:
        if a[-1] <= k//2:
            print("Impossible")
            exit()
        if d[k//2+1] != 2:
            print("Impossible")
            exit()
        for i in range(k//2+2,k+1):
            if d[i] < 2:
                print("Impossible")
                exit()
    else:
        if a[-1] < k//2:
            print("Impossible")
            exit()
        if d[k//2] != 1:
            print("Impossible")
            exit()
        for i in range(k//2+1,k+1):
            if d[i] < 2:
                print("Impossible")
                exit()
    print("Possible")



    return

if __name__ == '__main__':
    main()

Solution (Python):
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 = m = a.count(x[0]) != 2
    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")

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

mx = max(A)
cnt = [0] * 200

for i in A:
  cnt[i] += 1

inc = []
NN = mx + 1
while NN > 0:
  tm = min(2, NN)
  cnt[mx] -= tm
  
  if cnt[mx] < 0:
    print("Impossible")
    exit(0)
  inc.append(mx)
  mx -= 1
  NN -= tm

for i in inc[:-1]:
  cnt[i] = 0

for i in cnt:
  if i > 0:
    print("Impossible")
    exit(0)

print("Possible")

Solution (Python):
N=int(input())
a=list(map(int,input().split()))
M=max(a)
data=[0 for i in range(N)]
for i in range(N):
    data[a[i]]+=1

if M%2==0:
    check="Possible"
    for i in range(M//2+1,M+1):
        if data[i]<2:
            check="Impossible"
    if data[M//2]!=1:
        check="Impossible"
    print(check)
else:
    check="Possible"
    for i in range((M+1)//2+1,M+1):
        if data[i]<2:
            check="Impossible"
    if data[(M+1)//2]!=2:
        check="Impossible"
    print(check)

Solution (Python):
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:
    if c[l[0]]!=2:
        im()
    for i in range(l[0]+1,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()

Solution (Python):
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 cnt[0] == 2 and all(c >= 2 for c in cnt[1:]):
        print('Possible')
    else:
        print('Impossible')
else:
    print('Impossible')

Solution (Python):
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()
n = min(A)
if m%2==1:
  if Cnt[n]!=2:
    print('Impossible')
    sys.exit()
else:
  if Cnt[n]!=1:
    print('Impossible')
    sys.exit()
print('Possible')

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a.sort()

import collections
d = collections.Counter(a)

if -(-max(a)//2) != min(a):
    print("Impossible")
    exit()

if max(a)%2==0:
    if d[min(a)]!=1:
        print("Impossible")
        exit()
else:
    if d[min(a)]!=2:
        print("Impossible")
        exit()

for num in range(min(a)+1,max(a)+1):
    if d[num]<2:
        print("Impossible")
        exit()

print("Possible")

Solution (Python):
from collections import Counter
n = int(input())
A = list(map(int, input().split()))
k = max(A)
m = min(A)
C = Counter(A)
if m < (k+1)//2:
  print("Impossible")
else:
  if k & 1:
    for i in range((k+3)//2, k+1):
      if i not in C or C[i] < 2:
        print("Impossible")
        exit()
    if not (k+1)//2 in C or C[(k+1)//2] != 2:
      print("Impossible")
      exit()
  else:
    for i in range(1+k//2, k+1):
      if i not in C or C[i] < 2:
        print("Impossible")
        exit()
    if k//2 not in C or C[k//2] != 1:
      print("Impossible")
      exit()
  print("Possible")

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
t = max(a)
p = [0]*(t+1)
for x in a:
  p[x] += 1
if t%2:
  if any(p[:t//2+1]) or p[t//2+1] != 2 or min(p[t//2+1:]) < 2:
    print('Impossible')
  else:
    print('Possible')
else:
  if any(p[:t//2]) or p[t//2] != 1 or min(p[t//2+1:]) < 2:
    print('Impossible')
  else:
    print('Possible')

Solution (Python):
from collections import Counter
n=int(input())
a=Counter(list(map(int,input().split())))
b=[]
for i in a:
    b.append([i,a[i]])
b.sort()
x=b[-1][0]
if b[0][0]!=(x+1)//2:
    print("Impossible")
    exit()
if not(x%2==0 and b[0][1]==1 or x%2==1 and b[0][1]==2):
    print("Impossible")
    exit()
if x>n-1:
    print("Impossible")
    exit()
n=len(b)
cnt=2
k=b[0][0]  

for i in range(1,n):
    if b[i][1]<2 or b[i][1]<cnt or b[i][0]!=k+1:
        
        print("Impossible")
        exit()
    b[i][1]=cnt
    k+=1
print("Possible")

Solution (Python):
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 and a[0]>1:print("Impossible");exit()
print("Possible")

Solution (Python):
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 mi < mx // 2:
        return False

    if mx % 2 == 0 and cntA[mi] > 1:
        return False
    if mx % 2 == 1 and cntA[mi] > 2:
        return False

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

    return True

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

Solution (Python):
from collections import Counter
def main():
    N,*A=map(int, open(0).read().split())
    ans=True
    C=Counter(A)
    m=min(A)
    M=max(A)
    if C[m]>2:
        ans=False
    if N>2 and m==1:
        if C[1]!=1:
            ans=False
    if C[m]==1:
        if m*2!=M:
            ans=False
    else:
        if m*2-1!=M:
            ans=False
    for i in range(m+1,M+1):
        if i not in C or C[i]<2:
            ans=False
    print("Possible" if ans else "Impossible")

if __name__ == "__main__":
    main()

Solution (Python):

n = int(input())
a = [int(i) for i in input().split()]

diameter = max(a)
mini     = min(a)

dic = dict()
for v in a:
    if v in dic:
        dic[v] += 1
    else:
        dic[v] = 1

        
        
for i in range(diameter+1):
    v = max(i, diameter - i)
    
    if (v not in dic) or dic[v]==0:
        print("Impossible")
        
        break
    else:
        dic[v] -= 1
else:
    threshold = (diameter+1)//2 
    if threshold < mini: 
        print("Impossible")
    elif dic[mini]>0:
        print("Impossible")
    else:
        print("Possible")

Solution (Python):
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)]


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)
if len(mnl) > 2:
  print("Impossible")
  exit(0)
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])


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

Solution (Python):
_,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+2==c[-~m//2]and all(c[i+1]>1for i in range(m//2,m))and'Possible'or'Impossible')

Solution (Python):
_,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+2==c[-~m//2]and all(c[i+1]>1for i in range(m//2,m))and'Possible'or'Impossible')

Solution (Python):
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()


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:
        for i in range(1,len(L)):
            if L[i][0]==L[i-1][0]+1 and L[i][1]>=2:
                continue
            else:
                print("Impossible")
                exit()
        print("Possible")
    else:
        print("Impossible")
else:
    if L[-1][0]//2==L[0][0] and L[0][1]==1:
        for i in range(1,len(L)):
            if L[i][0]==L[i-1][0]+1 and L[i][1]>=2:
                continue
            else:
                print("Impossible")
                exit()
        print("Possible")
    else:
        print("Impossible")

Solution (Python):
import sys
N = int(input())
a = list(map(int, input().split()))
count = [0]*N
for ai in a:
    count[ai]+=1
m = max(a)
if min(a)<m-m//2:
    print('Impossible')
    sys.exit()
flag = True
for i in range(m, m-m//2-1, -1):
    if m%2 == 0 and i == m//2:
        if count[i] != 1:
            flag = False
            break
    elif m%2 == 1 and i == m//2+1:
        if count[i] != 2:
            flag = False
            break
    else:
        if count[i] <= 1:
            flag = False
            break
if flag:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
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]!=1:
        flg=0
    else:
      if c[i]!=2:
        flg=0
  else:
    if c[i]<=1:
      flg=0
if flg:
  print("Possible")
else:
  print("Impossible")

Solution (Python):


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())

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

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

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 2 > v:
        print('Impossible')
        exit()
print('Possible')

Solution (Python):


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 2 > v:
        print('Impossible')
        exit()
print('Possible')

Solution (Python):
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):
    if any(C[i] < 2 for i in range(mi + 1, ma)):
        print("Impossible")
    else:
        print("Possible")
else:
    print("Impossible")