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):
n = int(input())

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

a = sorted(a)

m = a[-1]
f = 1
if m % 2 == 1:
    s = m // 2 + 1
    count = 0
    if n == 2:
        if a[0] != 1 or a[1] != 1:
            f = 0
    elif a[0] != s or a[2] == s:
        f = 0
    else:
        for i in range(n):
            if a[i] < s:
                continue
            elif a[i] == s:
                if count == 0:
                    count = 1
                else:
                    count = 0
                    s += 1
            else:
                f = 0
                break
        if count == 1:
            f = 0
else:
    s = m // 2 + 1
    count = 0
    if a[0] != s-1 or a[1] == s-1:
        f = 0
    else:
        for i in range(1, n):
            if a[i] < s:
                continue
            elif a[i] == s:
                if count == 0:
                    count = 1
                else:
                    count = 0
                    s += 1
            else:
                f = 0
                break
        if count == 1:
            f = 0
        
if f == 1:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
m,s = a[-1],a[0]
if m!=a[-2] or (m+1)//2!=s or (m%2 and s-a[1]) or ((not m%2) and s==a[1]) or any(a.count(i)<2 for i in range(s+1,m)) or (n!=2 and s==a[1]==a[2]): print("Impossible")
else: print("Possible")

Solution (Python):
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
ok = True

d_max = max(a)
if n > 2 and d_max == 1:
	ok = False
if c[d_max] == 1:
	ok = False
else:
	if d_max % 2 == 0:
		d_min = d_max // 2
		if min(a) < d_min:
			ok = False
		if c[d_min] != 1:
			ok = False
		for d in range(d_min + 1, d_max):
			if c[d] < 2:
				ok = False

	else:
		d_min = (d_max + 1) // 2
		if min(a) < d_min:
			ok = False
		if c[d_min] != 2:
			ok = False
		for d in range(d_min + 1, d_max):
			if c[d] < 2:
				ok = False

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

Solution (Python):
def check(a):
    a = sorted(a)
    d = {}
    for x in a:
        if x not in d.keys():
            d[x] = 1
        else:
            d[x] += 1
    if (a[-1]+1)>>1 != a[0]:
        return False
    if (a[-1]&1) != 1 and d[a[0]]!=1:
        return False
    if (a[-1]&1) == 1 and d[a[0]]!=2:
        return False
    for i in xrange(a[-1], a[0], -1):
        if i not in d.keys() or d[i]<2:
            return False
    return True

def main():
    n = int(raw_input().strip())
    a = [int(x) for x in raw_input().strip().split()]
    if check(a):
        print 'Possible'
    else:
        print 'Impossible'

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")


def solve(c):
    max_length = max(c)
    for i in range(max_length, max_length // 2, -1):
        if c[i] < 2:
            return False

    if max_length % 2 == 0:
        if c[max_length // 2] != 1:
            return False
    else:
        if c[max_length - max_length // 2] != 2:
            return False

    return True


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


if __name__ == '__main__':
    main()

Solution (Python):
p = "Possible"
imp = "Impossible"

n = int(raw_input())
a = map(int, raw_input().split())
mx = max(a)
mn = min(a)
if mx == 1 and  mn == 1:
    if n == 2:
        print p
        exit()
    else:
        print imp
        exit()
cnt = [0] * 100
for i in xrange(n):
    cnt[a[i]] += 1
if mx % 2 == 0:
    if mx / 2 != mn:
        print imp
        exit()
    if cnt[mn] != 1:
        print imp
        exit()
    for i in xrange(mn + 1, mx + 1):
        if cnt[i] < 2:
            print imp
            exit()

else:
    if mx / 2 + 1 != mn:
        print imp
        exit()
    if cnt[mn] != 2:
        print imp
        exit()
    for i in xrange(mn + 1, mx + 1):
        if cnt[i] < 2:
            print imp
            exit()
print p

Solution (Python):
def solve():
    n=int(input())
    a=list(map(int,input().split()))
    a.sort()
    mina=a[0]
    maxa=a[-1]
    if (a[-1]+1) // 2 != mina:
        return False

    b=[0]*n
    for v in a:
        b[v] += 1
    if (maxa & 1) > 0:
        if b[mina] != 2:
            return False
    elif b[mina] != 1:
        return False

    for v in range(mina+1, maxa+1):
        if b[v] < 2:
            return False
    return True

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

Solution (Python):
import sys

def solve(A):
    nc = 1
    while nc < len(A) and A[nc] == A[0]:
        nc += 1
    if nc > 2:
        return False
    for i in xrange(1, len(A)):
        if A[i] - A[i-1] > 1:
            return False
    c = 2
    prev = -1
    for j in xrange(nc, len(A)):
        if A[j] == prev:
            c += 1
        else:
            if c < 2:
                return False
            prev = A[j]
            c = 1
    if c < 2:
        return False
    if nc == 1:
        return A[0] * 2 == A[-1]
    else:
        return A[0] * 2 - 1 == A[-1]

sys.stdin.readline()
A = map(int, sys.stdin.readline().split())
A.sort()
print "Possible" if solve(A) else "Impossible"

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A.sort()
maxv1 = A[-1]
maxv2 = A[-2]
if maxv1 != maxv2:
    print("Impossible")
    exit()

K = maxv1
if K % 2 == 0:
    for i in range(K // 2):
        for j in range(2):
            if K - i in A:
                A.remove(K - i)
            else:
                print("Impossible")
                exit()
    if K // 2 in A:
        A.remove(K // 2)
    else:
        print("Impossible")
        exit()
else:
    for i in range(K // 2 + 1):
        for j in range(2):
            if K - i in A:
                A.remove(K - i)
            else:
                print("Impossible")
                exit()
if len(A) == 0:
    print("Possible")
    exit()
else:
    for a in A:
        if K % 2 == 0:
            if a < K // 2 + 1:
                print("Impossible")
                exit()
        else:
            if a < (K + 1) // 2 + 1:
                print("Impossible")
                exit()
    print("Possible")

Solution (Python):
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')


def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())


def join(s):
    return ''.join(s)


def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)


def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m


def index(a, x):
    
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1


def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

nh=zip([1,0,-1,0],[0,1,0,-1])



n=i()
a=ii()
m=max(a)
if m%2==0:
    x=[m-j for j in range(m/2)]
    x=[m/2]+x+x
else:
    x=[m-j for j in range((m+1)/2)]
    x=x+x

for y in x:
    if y in a:
        a.remove(y)
    else:
        print "Impossible"
        break
else:
    if len(a)==0:
        print "Possible"
    else:
        if min(a)>=(m+1)/2+1:
            print "Possible"
        else:
            print "Impossible"

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

def resolve(a):
    if a == [1, 1]:
        return True

    if a.count(1) >= 2:
        return False

    max_num = max(a)
    min_num = min(a)

    if a.count(max_num) < 2:
        return False

    if max_num / 2 > min_num:
        return False

    if max_num & 1:
        
        for i in range(max_num // 2 + 1, max_num):
            if i not in a: return False

        if a.count(min_num) > 2:
            return False
    else:
        
        for i in range(max_num // 2, max_num):
            if i not in a: return False

        if a.count(min_num) > 1:
            return False
    return True

print("Possible" if resolve(a) else "Impossible")

Solution (Python):
from collections import Counter
n = input()
c = Counter(map(int, raw_input().split()))

ma = max(c)
mi = min(c)

if (ma+1)/2 == mi and c[mi] == (ma%2) + 1:
    if all(c[x] >= 2 for x in xrange(mi+1, ma+1)):
        print "Possible"
        exit(0)
print "Impossible"

Solution (Python):
n=int(raw_input())
a=map(int,raw_input().split())
maxa=max(a)
cmaxa=a.count(maxa)
ca=[0]*(maxa+1)
for i in xrange(n):
    ca[a[i]]+=1
if maxa%2==1:
    l=maxa/2+1
    if a.count(l)==2:
        for i in xrange(n):
            if a[i]<l:
                print("Impossible")
                exit()
        for i in xrange(l+1,maxa+1):
            if ca[i]<2:
                print("Impossible")
                exit()
        print("Possible")
    else:
        print("Impossible")
else:
    l=maxa/2
    if a.count(l)==1:
        for i in xrange(n):
            if a[i]<l:
                print("Impossible")
                exit()
        for i in xrange(l+1,maxa+1):
            if ca[i]<2:
                print("Impossible")
                exit()
        print("Possible")
    else:
        print("Impossible")

Solution (Python):
N = int(raw_input())
a = [int(x) for x in raw_input().split(' ')]

sorteda = sorted(a)

maxlen = sorteda[-1]
numpathsoflen = [0 for x in range(maxlen+1)]
if(sorteda[0] < (maxlen+1)/2):
    print 'Impossible'
else:
    for x in sorteda:
        numpathsoflen[x] += 1            
    valid = True
    starti = (maxlen+1)/2
    if(maxlen % 2 == 0):
        if(numpathsoflen[starti] != 1):
            valid = False
    else:
        if(numpathsoflen[starti] != 2):
            valid = False
    starti += 1        
    for x in range(starti, maxlen+1):
        if(numpathsoflen[x] < 2):
            valid = False
    if(valid):
        print 'Possible'
    else:
        print 'Impossible'

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

haves = [0] * (len(A) + 1)
for aa in xrange(max(A)+1):
    w = max(max(A) - aa, aa)
    haves[w] += 1

QQ = [0] * (len(A)+1)
for q in A:
    QQ[q] += 1 

Z = [QQ[x] - haves[x] for x in xrange(len(A)+1)]
if min(Z) < 0: print "Impossible"
else:

    waiting = [0] * (len(A) + 1)
    for z in reversed(xrange(len(A))):
        aa = A[z]
        if haves[aa] > 0:
            haves[aa]-=1
        else:
            waiting[aa] += 1



    for a in xrange(len(waiting)):
        if waiting[a] > 0:
            break

    if max(A) % 2 == 0:
        if a <= max(A) / 2:
            print "Impossible"
        else: print "Possible"
    else:
        if a <= (max(A)+1)/2:
            print "Impossible"
        else: print "Possible"

Solution (Python):



from collections import Counter

pos = "Possible"
imp = "Impossible"
def judge(nums):
    N = len(nums)
    count = Counter(nums)
    mx = max(nums)

    if mx == 1:
        if N == 2:
            return pos
        else:
            return imp
    elif mx == 2:
        if count[1] == 1 and count[2] >= 2:
            return pos
        else:
            return imp
    else:
        mid = (mx + 1) // 2

        for i in range(1, mid):
            if count[i] != 0:
                return imp
        if mx % 2 == 1:
            if count[mid] != 2:
                return imp
        else:
            if count[mid] != 1:
                return imp

        for i in range(mid+1, mx+1):
            if count[i] < 2:
                return imp

        return pos
                
dummy = int(input())
nums = list(map(int,input().split()))
print(judge(nums))


def mk(array):
    ret = []
    n = 1
    for e in array:
        ret += [n] * e
        n += 1
    print(ret)
    return ret

Solution (Python):
from sys import stdin
def main():
    n = int(stdin.readline())
    a = map(int, stdin.readline().split())
    b = [0] * (n + 1)
    for x in a:
        b[x] += 1
    m = max(a)
    l = 0
    r = m
    f = []
    while l <= r:
        b[r] -= 1
        if l < r:
            b[m-l] -= 1
        l += 1
        r -= 1
        if l <= r:
            f.append(max(m - l + 1, r + 1))
    for x in f:
        if b[x] > 0:
            b[x] = 0
    print "Possible" if all(not x for x in b) else "Impossible"
main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    i = 1
    if n > 2 and a[-1] == 1:
        return 'Impossible'
    if a[-1] != a[-2]:
        return 'Impossible'
    if a[-1] % 2 == 1:
        if a[-1] // 2 + 1 != a[0]:
            return 'Impossible'
        if a[0] != a[1]:
            return 'Impossible'
        if n > 2 and a[0] == a[2]:
            return 'Impossible'
        i = 2
    else:
        if a[-1] // 2 != a[0]:
            return 'Impossible'
        if a[0] == a[1]:
            return 'Impossible'
    c = 2
    t = a[0]
    for j in range(i,n):
        if t != a[j]:
            if c < 2:
                return 'Impossible'
            if t + 1 != a[j]:
                return 'Impossible'
            c = 0
            t = a[j]
        c += 1
    return 'Possible'

print(f())

Solution (Python):

import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

def solve():
    N = int(raw_input())
    a = map(int, raw_input().split())
    if N == 2 and a == [1, 1]:
        return True

    cnt = [0]*(N + 1)
    for ai in a:
        cnt[ai] += 1

    mx = max(a)
    l, r = 0, mx
    for i in xrange(1, mx):
        l += 1
        r -= 1
        cnt[max(l, r)] -= 1

    if cnt[mx] < 2: return False
    for i in xrange(1, (mx + 1)/2 + 1):
        if cnt[i] > 0:
            return False
    for i in xrange(1, N):
        if cnt[i] < 0:
            return False
    return True

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

Solution (Python):
from collections import defaultdict

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

def no():
    print("Impossible")
    quit(0)

def yes():
    print("Possible")
    quit(0)

cnts = defaultdict(int)
for x in xs:
    cnts[x] += 1

d = max(xs)
delems = []
for i in range(d+1):
    delems.append(max(i, d - i))

for delem in delems:
    if cnts[delem] <= 0:
        no()
    cnts[delem] -= 1

minx = min(delems) + 1
for x, rem in cnts.items():
    if rem > 0:
        if not minx <= x <= d:
            no()
yes()

Solution (Python):


from collections import Counter
def rl(s): return xrange(len(s))


INF = 2147483647


import sys
stdin = sys.stdin

N =        int( stdin.readline().strip() )

dists = map(int, stdin.readline().strip().split())

counts = Counter(dists)

if counts[1] == 2 and N == 2:
    print "Possible"
elif counts[1] >= 2:
    print "Impossible"
else:
    m = max(dists)
    good = True
    if counts[m] < 2:
        good = False
    if m % 2 == 0 and counts[m//2] != 1:
        good = False
    if m % 2 == 1 and counts[m//2 + 1] != 2:
        good = False
    for i in range(m//2 + 1, m):
        if counts[i] < 2:
            good = False
    if good:
        print "Possible"
    else:
        print "Impossible"