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 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 and 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]+1)//2:
            q=0
            break
        elif a[i][0]!=a[-1][0]+i-len(a)+1:
            q=0
            break
        elif a[i][0]==(a[-1][0]+1)//2 and a[i][1]!=2:
            q=0
            break
        elif a[i][1]<2:
            q=0
            break
if q:
    print("Possible")
else:
    print("Impossible")

Solution (Python):

N = int(input())

a = list(map(int,input().split()))
maxi = max(a)

dic = {}

for i in range(N):

    if a[i] not in dic:
        dic[a[i]] = 1
    else:
        dic[a[i]] += 1

flag = True

if maxi % 2 == 0:

    for i in range(maxi + 1):

        if i < maxi // 2 and i in dic:
            flag = False

        if i == maxi // 2 and (i not in dic or dic[i] != 1):
            flag = False

        if i > maxi // 2 and (i not in dic or dic[i] < 2):
            flag = False

else:

    for i in range(maxi + 1):

        if i <= maxi // 2 and i in dic:
            flag = False

        if i == maxi // 2 + 1 and (i not in dic or dic[i] != 2):
            flag = False

        if i > maxi // 2 + 1 and (i not in dic or dic[i] < 2):
            flag = False

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

Solution (Python):
import collections

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

A.sort()
C = collections.Counter(A)

mx = A[-1]
mn = A[0]

flag = True

if mx % 2 == 0:
    if mn != mx // 2:
        flag = False
    if C[mn] != 1:
        flag = False
else:
    if mn != mx // 2 + 1:
        flag = False
    if C[mn] != 2:
        flag = False

for i in range(mn + 1, mx + 1):
    if C[i] < 2:
        flag = False
        break

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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
from collections import defaultdict
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    D=defaultdict(int)
    for a in A: D[a]+=1

    m=max(A)
    B=list(range(m//2+1,m+1))*2
    if(m&1==0): B.append(m//2)

    for b in B:
        if(D[b]==0):
            print("Impossible")
            return
        D[b]-=1

    s=min(B)
    for key,val in D.items():
        if(val==0): continue
        if(not (s+1<=key<=m)):
            print("Impossible")
            return

    print("Possible")
resolve()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・直径の長さをdとする。だいたい、半径より下の長さは存在できない
・だいたいd/2より上は任意に足せる。ただし中心は1組のみ
"""

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

def test(A):
    D = max(A)
    r = (D+1)//2
    counter = [0] * (D+1)
    for x in A:
        counter[x] += 1
    if (D&1) and (counter[r] != 2):
        return False
    if (not (D&1)) and (counter[r] != 1):
        return False
    if any(x < r for x in A):
        return False
    if any(counter[x] <= 1 for x in range(r+1,D+1)):
        return False
    return True

answer = 'Possible' if test(A) else 'Impossible'

print(answer)

Solution (Python):
n=int(input())
A=[int(i) for i in input().split()]+[0]
m=max(A)
import collections
C=collections.Counter(A)
chk=True
if m%2==0:
  for i in range(m//2,m+1):
    if i==m//2:
      if C[i]!=1:
        chk=False
    else:
      if C[i]<2:
        chk=False
else:
  for i in range((m+1)//2,m+1):
    if i==(m+1)//2:
      if C[i]!=2:
        chk=False
    else:
      if C[i]<2:
        chk=False
print("Possible" if chk else "Impossible")

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time

def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 +10 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase


input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

ans='Possible'
n=I()
a=LI()
M=max(a)
m=min(a)
c=[0]*(M+1)
for i in range(n):
    c[a[i]]+=1
    
if all([c[i]>=2 for i in range(m+1,M+1)]):
    0
else:
    ans='Impossible'

if c[m]!=1+M%2:
    ans='Impossible'
    
print(ans)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time

def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 +10 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase


input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

ans='Possible'
n=I()
a=LI()
M=max(a)
m=min(a)
c=[0]*(M+1)
for i in range(n):
    c[a[i]]+=1
if sum([min(c[i],1) for i in range(m,M+1)])!=M-m+1:
    ans='Impossible'
if c[m]!=1+M%2:
    ans='Impossible'
    
print(ans)

Solution (Python):
def main():
    from collections import Counter as ct
    n = int(input())
    a = list(map(int, input().split()))
    c = ct(a)
    min_a = min(a)
    max_a = max(a)
    if min_a == 1:
        if c[min_a] == 1:
            pass
        elif a == [1, 1]:
            print("Possible")
            return 0
        else:
            print("Impossible")
            return 0
    if c[min_a] == 1 and (max_a+1)//2 > min_a:
        print("Impossible")
        return 0
    if c[min_a] == 2 and (max_a+2)//2 > min_a:
        print("Impossible")
        return 0
    if c[min_a] > 2:
        print("Impossible")
        return 0
    for i in range(min_a+1, max_a+1):
        if c[i] < 2:
            print("Impossible")
            return 0
    print("Possible")
main()

Solution (Python):
from collections import Counter

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

def solve() :
    cnt = list(Counter(a).items())
    cnt.sort()
    
    if cnt[0][1] == 1 and cnt[-1][0] != 2 * cnt[0][0] :
        return 'Impossible'
    if cnt[0][1] == 2 and cnt[-1][0] != 2 * cnt[0][0] - 1 :
        return 'Impossible'
    if cnt[0][1] > 2 :
        return 'Impossible'

    for i in range(1, len(cnt)) :
        if cnt[i][0] != cnt[i-1][0] + 1 :
            return 'Impossible'
        if cnt[i][1] < 2 :
            return 'Impossible'
            
    return 'Possible'
    
print(solve())

Solution (Python):
import numpy as np

def checker(n ,da):
    mx = max(da)
    mi = min(da)
    if n == 2:
        return (da == [1, 1])
    if mx < 2 or n <= mx: return False
    arr = np.zeros(mx + 1, dtype=int)
    for i in range(n):
        arr[da[i]] += 1
    if mx % 2:
        if arr[mi] > 2 or (mx + 1) // 2 != mi:
            return False
    else:
        if arr[mi] > 1 or mx // 2 != mi:
            return False
    for i in range(mi, mx):
        if arr[i + 1] < 2:
            return False
    return True

    

def main():
    n = int(input())
    da = list(map(int,input().split()))
    print('Possible') if checker(n, da) else print('Impossible')
    return

if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter

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

    m = max(A)

    dic = {}
    for n in range((m+1)//2, m+1):
        dic[n] = 0

    for a in A:
        if not a in dic.keys():
            return False
        else:
            dic[a] += 1

    if m % 2 == 0:
        half = m//2
        if dic[half] != 1:
            return False
    else:
        half = m//2+1
        if dic[half] != 2:
            return False
    for n in range(half+1, m+1):
        if dic[n] < 2:
            return False
    return True


if __name__ == "__main__":
    if solve():
        print('Possible')
    else:
        print('Impossible')

Solution (Python):
from collections import Counter


def solve(n, aaa):
    if n == 2:
        return aaa == [1, 1]

    count = Counter(aaa)
    min_a = min(count)
    max_a = max(count)
    
    if not 2 <= max_a <= n - 1:
        return False
    
    if min_a != (max_a + 1) // 2:
        return False
    
    if count[min_a] != max_a % 2 + 1:
        return False
    
    if any(count[a] < 2 for a in range(min_a + 1, max_a + 1)):
        return False
    
    return True


n = int(input())
aaa = list(map(int, input().split()))
print('Possible' if solve(n, aaa) else 'Impossible')

Solution (Python):
from collections import defaultdict

def getlist():
	return list(map(int, input().split()))


def main():
	N = int(input())
	D = defaultdict(int)
	a = sorted(getlist())
	if N == 2:
		if a[0] != 1 or a[1] != 1:
			print("Impossible")
		else:
			print("Possible")
	else:
		for i in range(N):
			D[a[i]] += 1
		if a[-1] % 2 != 0:
			if a[0] * 2 - 1 != a[-1]:
				print("Impossible")
			else:
				judge = "Possible"
				if D[a[0]] != 2:
					judge = "Impossible"
				for i in range(a[0], a[-1] + 1):
					if D[i] < 2:
						judge = "Impossible"
						break
				print(judge)
		else:
			judge = "Possible"
			if a[0] * 2 != a[-1]:
				print("Impossible")
			else:
				judge = "Possible"
				if D[a[0]] != 1:
					judge = "Impossible"
				for i in range(a[0] + 1, a[-1] + 1):
					if D[i] < 2:
						judge = "Impossible"
						break
				print(judge)

if __name__ == '__main__':
	main()

Solution (Python):
from collections import Counter


def check(N, A):
    d = max(A)
    if d >= N:
        return False
    c = Counter(A)
    cnt = 0
    if d % 2 == 0:
        if c[d//2] != 1:
            return False
        cnt += 1
        mn = d//2+1
    else:
        if c[d//2+1] != 2:
            return False
        cnt += 2
        mn = d//2+2
    for i in range(mn, d+1):
        if c[i] < 2:
            return False
        cnt += c[i]
    return cnt == N


def main():
    N = int(input())
    A = list(map(int, input().split()))
    if check(N, A):
        print("Possible")
    else:
        print("Impossible")


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
def solve():
    d = {}
    r = max(a)
    mi = (r+1)//2
    for i in a:
        if i < mi:
            return False
        d[i] = d.get(i, 0) + 1

    if not(mi in d and d[mi] == 1+r%2):
        return False
    for i in range(mi+1, r+1):
        if i not in d or d[i] < 2:
            return False
    return True

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

from collections import defaultdict


def main():
    n = int(input())
    a = list(map(int, input().split()))
    maxa = max(a)
    mina = min(a)
    dica = defaultdict(lambda: 0)
    for _a in a:
        dica[_a] += 1
    if dica[maxa] < 2:
        print("Impossible")
    elif mina != (maxa+1)//2:
        print("Impossible")
    else:
        if ((maxa+1)%2 == 1 and dica[mina] != 1) or ((maxa+1)%2 == 0 and dica[mina] != 2):
            print("Impossible")
        else:
            mina += 1
            for _a in range(mina, maxa+1):
                if _a not in dica or dica[_a] < 2:
                    print("Impossible")
                    break
            else:
                print("Possible")


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
cntA = Counter(A)
valA= list(set(A))
valA.sort()

if valA[-1] % 2 == 1:
    if valA[0] != -(-valA[-1] // 2) or cntA[valA[0]] != 2:
        print('Impossible')
        exit()

    for a in range(valA[0], valA[-1] + 1):
        if cntA[a] < 2:
            print('Impossible')
            exit()
else:
    if valA[0] != valA[-1] // 2 or cntA[valA[0]] != 1:
        print('Impossible')
        exit()

    for a in range(valA[0] + 1, valA[-1] + 1):
        if cntA[a] < 2:
            print('Impossible')
            exit()

print('Possible')

Solution (Python):
from collections import Counter, deque

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

cntA = Counter(A)
valA = list(set(A))
valA.sort(reverse=True)

pathLeng = [0] * (N + 1)

if cntA[valA[0]] < 2 or cntA[valA[-1]] > 2:
    print('Impossible')
    exit()

pathLeng[1] = valA[0]
pathLeng[2] = valA[0]
cntA[valA[0]] -= 2
maxNode = 2

pr = [[] for _ in range(N + 1)]
ch = [[] for _ in range(N + 1)]

for i, a in enumerate(valA[1:], start=2):
    if a == valA[-1] and cntA[valA[-1]] == 1:
        prevLeft = maxNode
        prevRight = maxNode - 1
        maxNode += 1
        ch[prevLeft].append(maxNode)
        ch[prevRight].append(maxNode)
        pr[maxNode].append(prevLeft)
        pr[maxNode].append(prevRight)
        pathLeng[maxNode] = valA[-1]
        cntA[valA[-1]] -= 1
        break

    prevLeft = (i - 1) * 2 - 1
    prevRight = (i - 1) * 2
    nowLeft = i * 2 - 1
    nowRight = i * 2

    maxNode = max(maxNode, nowRight)
    if maxNode > N:
        print('Impossible')
        exit()

    pathLeng[nowLeft] = a
    pathLeng[nowRight] = a

    cntA[a] -= 2

    ch[prevLeft].append(nowLeft)
    ch[prevRight].append(nowRight)
    pr[nowLeft].append(prevLeft)
    pr[nowRight].append(prevRight)
else:
    ch[maxNode].append(maxNode - 1)
    pr[maxNode - 1].append(maxNode)

for a, c in cntA.items():
    for _ in range(c):
        maxNode += 1
        i = pathLeng.index(a)
        ch[maxNode].append(ch[i][0])
        pr[ch[i][0]].append(maxNode)
        pathLeng[maxNode] = a
        cntA[a] -= 1

def search(index):
    visited = [False] * (N + 1)
    visited[index] = True
    st = deque([(index, 0)])
    ret = 0

    while st:
        now, d = st.pop()
        ret = max(ret, d)

        for to in pr[now]:
            if not visited[to]:
                st.append((to, d + 1))
                visited[to] = True
        for to in ch[now]:
            if not visited[to]:
                st.append((to, d + 1))
                visited[to] = True
    return ret

for i, d in enumerate(pathLeng[1:], start=1):
    if search(i) != d:
        print('Impossible')
        exit()

for v in cntA.values():
    if v != 0:
        print('Impossible')
        exit()

A.sort()
pathLeng.sort()

if A == pathLeng[1:]:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
N = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
yes = 'Possible'
no = 'Impossible'

if N == 2:
    if a[0] != 1 and a[1] != 1:
        print(no)
        exit()
    else:
        print(yes)
        exit()
if a[-1] != (a[0] + 1) // 2:
    print(no)
    exit()
else:
    if a[0] % 2 == 0:
        if a[-2] == a[-1]:
            print(no)
            exit()
    else:
        if a[-3] == a[-1]:
            print(no)
            exit()

ok = [0] * N
for i in range(N):
    ok[a[i]] += 1
for i in range(a[-1] + 1, a[0] + 1):
    if ok[i] < 2:
        print(no)
        exit()

print(yes)

Solution (Python):
from collections import defaultdict
N = int(input())
A = [int(x) for x in input().split()]
D = defaultdict(int)
for a in A:
  D[a] += 1
if D[1] == 2 and N > 2:
  print('Impossible')
elif D[min(A)] > 2:
  print('Impossible')
elif -(-max(A) // 2) != min(A):
  print('Impossible')
elif D[min(A)] != 1 + (max(A) % 2):
  print('Impossible')
else:
  for a in range(min(A) + 1, max(A) + 1):
    if D[a] < 2:
      print('Impossible')
      break
  else:
    print('Possible')

Solution (Python):
from collections import Counter

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

c = Counter(a)
m = max(a)



flag = True

for i in range(1, m+1):
    if i<m//2:
        if c[i]!=0:
            flag = False
    elif i==m//2:
        if m%2 == 0:
            if c[i]!=1:
                flag = False
                break
        else:
            if c[i]!=0:
                flag = False
                break
    elif i == m//2+1:
        if m%2 == 0:
            if c[i]<2:
                flag = False
                break
        else:
            if c[i]!=2:
                flag = False
                break
    else:
        if c[i]<2:
            flag = False
            break

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

Solution (Python):
from collections import Counter

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

c = Counter(a)
m = max(a)

flag = True

if m%2 == 0:
    for i in range(1,m+1):
        if i<m//2:
            if c[i]!=0:
                flag = False
                break
        elif i==m//2:
            if c[i]!=1:
                flag = False
                break
        else:
            if c[i]<2:
                flag = False
                break
else:
    for i in range(1,m+1):
        if i<=m//2:
            if c[i]!=0:
                flag = False
                break
        elif i==m//2+1:
            if c[i]!=2:
                flag = False
                break
        else:
            if c[i]<2:
                flag = False
                break

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

n = getN()
nums = getList()


mx = max(nums)
mn = (mx+1) // 2
mndx = (mx % 2) + 1

from collections import Counter

cnt = Counter(nums)

for i in range(mn+1, mx+1):
    if cnt[i] < 2:
        print("Impossible")
        sys.exit()

if cnt[mn] != mndx:
    print("Impossible")
else:
    print("Possible")

Solution (Python):
from collections import defaultdict
N=int(input())
A=list(map(int,input().split()))
def solve(N,A):
    dic=defaultdict(lambda: 0)
    for a in A: dic[a]+=1
    m=max(A)
    for i in range((m+1)//2,m+1):
        if m%2==0 and i==m//2:
            dic[i]-=1
        else:
            dic[i]-=2
    return not any([cnt<0 or (n<((m-m//2)+1) and cnt>0) for n,cnt in dic.items()])

print("Possible" if solve(N,A) else "Impossible")

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

cnt = {}
for i in range(n):
    if a[i] not in cnt:
        cnt[a[i]] = 1
    else:
        cnt[a[i]] += 1

max_a = max(a)
min_ = 10000000000
diameter = max_a + 1
for i in range(diameter):
    tmp = max(max_a - i, i)
    min_ = min(min_, tmp)
    if tmp not in cnt:
        print("Impossible")
        exit()
    if cnt[tmp] == 0:
        print("Impossible")
        exit()
    cnt[tmp] -= 1

for i in cnt:
    if cnt[i] > 0 and i <= min_:
        print("Impossible")
        exit()
print("Possible")

Solution (Python):
n = int(input())
a = [int(item) for item in input().split()]

if n == 2:
    if a[0] == 1 and a[1] == 1:
        print("Possible")
        exit()
    else:
        print("Impossible")
        exit()

cnt = [0] * 100
for item in a:
    cnt[item] += 1

maxa = max(a)
mina = (maxa + 1) // 2

ans = True
for i in range(100):
    if i < mina:
        if(cnt[i] > 0):
            ans = False
    elif i == mina:
        if i == 1 and cnt[i] != 1:
            ans = False
        if i > 1:
            if maxa % 2 == 1 and not cnt[i] == 2:
                ans = False
            if maxa % 2 == 0 and not cnt[i] == 1:
                ans = False
    elif i > mina and i <= maxa: 
        if cnt[i] < 2:
            ans = False

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

Solution (Python):
import os
import sys
from collections import Counter

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

counts = Counter(A)
ma = max(A)
mi = min(A)
ok = True
if ma % 2 == 0:
    ok &= mi == ma // 2
    ok &= counts[mi] == 1
else:
    ok &= mi == ma // 2 + 1
    ok &= counts[mi] == 2
for d in range(ma, mi, -1):
    ok &= counts[d] >= 2
if ok:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

counts = Counter(A)
m = max(A)
ok = True
if m % 2 == 0:
    ok &= min(A) == max(A) // 2
    ok &= counts[min(A)] == 1
else:
    ok &= min(A) == max(A) // 2 + 1
    ok &= counts[min(A)] == 2
for d in range(max(A), min(A), -1):
    ok &= counts[d] >= 2
if ok:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
mi = min(A)
cntA = Counter(A)
cnt_mi = cntA[mi]
if cnt_mi>2:
    print("Impossible")
    exit()
elif cnt_mi==1:
    ma = 2 * mi
else:
    ma = 2 * mi - 1
cnt = cnt_mi
for i in range(mi+1, ma+1):
    c = cntA[i]
    if c < 2:
        print("Impossible")
        exit()
    cnt += c
if cnt!=N:
    print("Impossible")
else:
    print("Possible")

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from collections import Counter



N = int(input())
A = [int(x) for x in input().split()]

diag = max(A)

def solve_even():
    
    depth = [x-diag//2 for x in A]
    if any(x < 0 for x in depth):
        return False
    counter = Counter(depth)
    if counter[0] != 1:
        return False
    for i in range(1,diag//2+1):
        if counter[i] < 2:
            return False
    return True

def solve_odd():
    
    depth = [x-(diag+1)//2 for x in A]
    if any(x < 0 for x in depth):
        return False
    counter = Counter(depth)
    if counter[0] != 2:
        return False
    for i in range((diag+1)//2):
        if counter[i] < 2:
            return False
    return True

bl = solve_odd() if diag&1 else solve_even()
answer = 'Possible' if bl else 'Impossible'
print(answer)

Solution (Python):


from collections import deque, defaultdict
import itertools as ite
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N = input()
a = map(int, raw_input().split())

L = max(a)
m = defaultdict(int)
for num in a:
    if num < (L + 1) / 2:
        print "Impossible"
        exit()
    m[num] += 1
for num in range(L / 2 + 1, L + 1):
    if not num in m or m[num] < 2:
        print "Impossible"
        exit()
if L % 2 == 0 and (not L / 2 in m or m[L / 2] >= 2):
    print "Impossible"
    exit()
if L % 2 == 1 and m[L / 2 + 1] > 2:
    print "Impossible"
    exit()
print "Possible"

Solution (Python):
from collections import Counter
from sys import exit
def imp():
    print('Impossible')
    exit()

N = int(input())
A = list(map(int, input().split()))
mia = min(A)
maa = max(A)
if mia != -(-maa//2):
    imp()
if maa % 2:
    CA = Counter(A)
    if CA[mia] != 2:
        imp()
    for i in range(mia +1, maa+1):
        if CA[i] < 2:
            imp()
else:
    CA = Counter(A)
    if CA[mia] != 1:
        imp()
    for i in range(mia +1, maa+1):
        if CA[i] < 2:
            imp()
print('Possible')

Solution (Python):

import sys

YES = "Possible"  
NO = "Impossible"  

def solve(N: int, a: "List[int]"):
    amax = max(a)
    vmin = (amax + 1) // 2
    nmin = amax % 2 + 1

    for i in range(1, amax+1):
        if i < vmin and a.count(i) > 0:
            print(NO)
            return
        if i == vmin and a.count(i) != nmin:
            print(NO)
            return
        if i > vmin and a.count(i) < 2:
            print(NO)
            return
    print(YES)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [ int(next(tokens)) for _ in range(N) ]  
    solve(N, a)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter

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

maxA = max(As)
minA = (maxA+1) // 2
cnt = Counter(As)

for A, num in cnt.items():
    if A < minA:
        print('Impossible')
        break
    elif A == minA:
        if (maxA % 2 and num != 2) or (maxA % 2 == 0 and num != 1):
            print('Impossible')
            break
    elif num < 2:
        print('Impossible')
        break
else:
    for A in range(minA+1, maxA+1):
        if A not in cnt:
            print('Impossible')
            break
    else:
        print('Possible')

Solution (Python):
import sys
input=sys.stdin.readline
from math import ceil
input()
A=list(map(int,input().split()))
maxA=max(A)
minA=min(A)
if minA!=ceil(maxA/2):
    print('Impossible')
else:
    if maxA%2:
        for i in range(minA,maxA+1):
            if i==minA:
                if A.count(i)!=2:
                    print('Impossible')
                    break
            else:
                if A.count(i)<2:
                    print('Impossible')
                    break
        else:
            print('Possible')
    else:
        for i in range(minA,maxA+1):
            if i==minA:
                if A.count(i)!=1:
                    print('Impossible')
                    break
            else:
                if A.count(i)<2:
                    print('Impossible')
                    break
        else:
            print('Possible')

Solution (Python):
N=int(input())
A=[int(i) for i in input().split()]
D=max(A)
L=[0]*(D+1)
for i in range(N):
  L[A[i]]+=1
if D==1:
  if N>2:
    print("Impossible")
    exit()
elif D%2==0:
  for i in range(D+1):
    if i<D//2 and L[i]>0:
      print("Impossible")
      exit()
    elif i==D//2 and L[i]!=1:
      print("Impossible")
      exit()
    elif i>D//2 and L[i]<2:
      print("Impossible")
      exit()
elif D%2==1:
  for i in range(D+1):
    if i<D//2+1 and L[i]>0:
      print("Impossible")
      exit()
    elif i==D//2+1 and L[i]!=2:
      print("Impossible")
      exit()
    elif i>D//2+1 and L[i]<2:
      print("Impossible")
      exit()
print("Possible")

Solution (Python):
from collections import Counter as C

N = int(input())
A = [int(a) for a in input().split()]

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

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

Solution (Python):
from collections import defaultdict
import sys
N=int(input())
A=[int(i) for i in input().split()]
dd=defaultdict(int)
K=[0]*N
for a in A:
    dd[a]+=1
    K[a]+=1
L=list(dd.items())
L.sort()

if L[-1][1]<=1:
    print('Impossible')
    sys.exit()
m=L[-1][0]
if m%2==1:
    if L[0][0]!=m//2+1 or L[0][1]!=2:
        print('Impossible')
        sys.exit()
if m%2==0:
    if L[0][0]!=m//2 or L[0][1]!=1:
        print('Impossible')
        sys.exit()
s=L[0][0]
for i in range(s+1,m+1):
    if K[i]<=1:
        print('Impossible')
        sys.exit()
print('Possible')

Solution (Python):
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
ctr = Counter(A)
maxa = max(A)
mina = min(A)

def ok():
    if mina != (maxa+1)//2:
        return False
    if maxa%2:
        if ctr[mina] != 2: return False
    else:
        if ctr[mina] != 1: return False
    for n in range(mina+1, maxa+1):
        if ctr[n] < 2:
            return False
    return True

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