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(raw_input())
a=map(int,raw_input().split())
maxa=max(a)
cmaxa=a.count(maxa)
if cmaxa==1:
    print("Impossible")
    exit()
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()
        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()
        print("Possible")
    else:
        print("Impossible")

Submission status: Wrong Answer

Solution code:
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 cmaxa==1:
    print("Impossible")
    exit()
if maxa%2==1:
    l=maxa/2+1
    if a.count(l)==2:
        for i in xrange(l+1,maxa):
            if ca[i]>ca[i+1]:
                print("Impossible")
                exit()
        print("Possible")
    else:
        print("Impossible")
else:
    l=maxa/2
    if a.count(l)==1:
        for i in xrange(l+1,maxa):
            if ca[i]>ca[i+1]:
                print("Impossible")
                exit()
        print("Possible")
    else:
        print("Impossible")

Submission status: Wrong Answer

Solution code:
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 cmaxa==1:
    print("Impossible")
    exit()
if maxa%2==1:
    l=maxa/2+1
    if a.count(l)==2:
        for i in xrange(l+1,maxa):
            if ca[i]!=ca[i+1]:
                print("Impossible")
                exit()
        print("Possible")
    else:
        print("Impossible")
else:
    l=maxa/2
    if a.count(l)==1:
        for i in xrange(l+1,maxa):
            if ca[i]!=ca[i+1]:
                print("Impossible")
                exit()
        print("Possible")
    else:
        print("Impossible")

Submission status: Wrong Answer

Solution code:
n=int(raw_input())
a=map(int,raw_input().split())
maxa=max(a)
cmaxa=a.count(maxa)
if cmaxa==1:
    print("Impossible")
    exit()

if maxa%2==1:
    l=maxa/2+1
    if a.count(l)==2 and cmaxa*(maxa/2)+2<=n:
        print("Possible")
    else:
        print("Impossible")
else:
    l=maxa/2
    if a.count(l)==1 and cmaxa*(maxa/2)+1<=n:
        print("Possible")
    else:
        print("Impossible")

Submission status: Wrong Answer

Solution code:
n=int(raw_input())
a=map(int,raw_input().split())
maxa=max(a)
cmaxa=a.count(maxa)
if cmaxa==1:
    print("Impossible")

if maxa%2==1:
    l=maxa/2+1
    if a.count(l)==2 and cmaxa*(maxa/2)+2<=n:
        print("Possible")
    else:
        print("Impossible")
else:
    l=maxa/2
    if a.count(l)==1 and cmaxa*(maxa/2)+1<=n:
        print("Possible")
    else:
        print("Impossible")

Submission status: Wrong Answer

Solution code:
n=int(raw_input())
a=map(int,raw_input().split())
maxa=max(a)
if maxa%2==1:
    l=maxa/2+1
    if a.count(l)==2 and len(a)>maxa:
        print("Possible")
    else:
        print("Impossible")
else:
    l=maxa/2
    if a.count(l)==1 and len(a)>maxa:
        print("Possible")
    else:
        print("Impossible")

Submission status: Wrong Answer

Solution code:
n=int(raw_input())
a=map(int,raw_input().split())
maxa=max(a)
if maxa%2==1:
    l=maxa/2+1
    if a.count(l)==2:
        print("Possible")
    else:
        print("Impossible")
else:
    l=maxa/2
    if a.count(l)==1:
        print("Possible")
    else:
        print("Impossible")

Submission status: Wrong Answer

Solution code:
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            
    numnodes = maxlen+1
    valid = True
    starti = (maxlen+1)/2
    if(maxlen % 2 == 0):
        if(numpathsoflen[starti] != 1):
            valid = False
        starti += 1        
    for x in range(starti, maxlen+1):
        if(numpathsoflen[x] < 2):
            valid = False
        numnodes += numpathsoflen[x] - 2
    if(valid):
        print 'Possible'
    else:
        print 'Impossible'

Submission status: Wrong Answer

Solution code:
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            
    numnodes = maxlen+1
    valid = True
    starti = (maxlen+1)/2
    if(maxlen % 2 == 0):
        if(numpathsoflen[starti] != 1):
            valid = False
        starti += 1        
    for x in range(starti, maxlen+1):
        if(numpathsoflen[x] < 2):
            valid = False
        numnodes += numpathsoflen[x] - 2
    if(numnodes != N):
        valid = False
    if(valid):
        print 'Possible'
    else:
        print 'Impossible'

Submission status: Wrong Answer

Solution code:
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            
    numnodes = maxlen+1
    valid = True
    starti = (maxlen+1)/2
    if(maxlen % 2 == 0):
        if(numpathsoflen[starti] != 1):
            valid = False
        starti += 1        
    for x in range(starti, maxlen+1):
        if(numpathsoflen[starti] < 2):
            valid = False
        numnodes += numpathsoflen[x] - 2
    if(numnodes != N):
        valid = False
    if(valid):
        print 'Possible'
    else:
        print 'Impossible'

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from collections import Counter

N = int(input())
nums = list(map(int,input().split()))
count = Counter(nums)

pos = "Possible"
imp = "Impossible"

mx = max(nums)

def judge():
    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[mid] < 2:
                return imp

        return pos
                
print(judge())

Submission status: Wrong Answer

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

sorteda = sorted(a)

maxlen = sorteda[-1]
numpathsoflen = {}
if(sorteda[0] < (maxlen+1)/2):
    print 'Impossible'
elif(maxlen % 2 == 0 
     and sorteda[0] == maxlen/2 
     and sorteda[0] == sorteda[1]):
    print 'Impossible'
else:
    numnodes = maxlen + 1
    for i in range(N):
        if a[i] in numpathsoflen.keys():
            if numpathsoflen[a[i]] >= 2:
                numnodes += 1
            numpathsoflen[a[i]] += 1            
        else:
            numpathsoflen[a[i]] = 1
    if(numnodes != N):
        print 'Impossible'
    else:
        out= 'Possible'
        starti = (maxlen+1)/2 
        if maxlen % 2 == 0:
            starti += 1
        for i in range(starti, maxlen+1):
            if((not i in numpathsoflen.keys()) or numpathsoflen[i] < 2):
                out = 'Impossible'                
        print out

Submission status: Wrong Answer

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

sorteda = sorted(a)

maxlen = sorteda[-1]
numpathsoflen = {}
if(sorteda[0] < (maxlen+1)/2):
    print 'Impossible'
elif(maxlen % 2 == 0 
     and sorteda[0] == maxlen/2 
     and sorteda[0] == sorteda[1]):
    print 'Impossible'
else:
    numnodes = maxlen + 1
    for i in range(N):
        if a[i] in numpathsoflen.keys():
            if numpathsoflen[a[i]] >= 2:
                numnodes += 1
            numpathsoflen[a[i]] += 1            
        else:
            numpathsoflen[a[i]] = 1
    if(numnodes != N):
        print 'Impossible'
    else:
        out= 'Possible'
        starti = (maxlen+1)/2 
        if maxlen % 2 == 0:
            starti += 1
        for i in range(starti, maxlen):
            if(not i in numpathsoflen.keys() or numpathsoflen[i] < 2):
                out = 'Impossible'                
        print out

Submission status: Wrong Answer

Solution code:
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
            f.append(r)
        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()

Submission status: Wrong Answer

Solution code:
from sys import stdin
def main():
    n = int(stdin.readline())
    a = map(int, stdin.readline().split())
    L = range(n + 2)
    R = range(n + 2)
    b = [0] * (n + 2)
    L[n+1] = R[n+1] = n
    L[0] = R[0] = 1
    for i, x in enumerate(a, 1):
        b[x] = i
    s = 0
    for i in xrange(n, 0, -1):
        j = b[i]
        s += i * (R[j] - j + 1) * (j - L[j] + 1)
        R[L[j]-1] = R[j]
        L[R[j]+1] = L[j]
    print s
main()

Submission status: Wrong Answer

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

sorteda = sorted(a)

maxlen = sorteda[-1]
numpathsoflen = {}
if(sorteda[0] < (maxlen+1)/2):
    print 'Impossible'
elif(maxlen % 2 == 0 
     and sorteda[0] == maxlen/2 
     and sorteda[0] == sorteda[1]):
    print 'Impossible'
else:
    numnodes = maxlen + 1
    for i in range(N):
        if a[i] in numpathsoflen.keys():
            if numpathsoflen[a[i]] >= 2:
                numnodes += 1
            numpathsoflen[a[i]] += 1            
        else:
            numpathsoflen[a[i]] = 1
    if(numnodes != N):
        print 'Impossible'
    else:
        print 'Possible'

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

N = int(raw_input())
a = map(int, raw_input().split())
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

ans = True
if cnt[mx] < 2: ans = False
for i in xrange(1, (mx + 1)/2 + 1):
    if cnt[i] > 0:
        ans = False
for i in xrange(1, N):
    if cnt[i] < 0:
        ans = False
print "Possible" if ans else "Impossible"

Submission status: Wrong Answer

Solution code:
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'
            c = 0
            t = a[j]
        c += 1
    return 'Possible'

print(f())

Submission status: Wrong Answer

Solution code:
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'
        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'
            c = 0
            t = a[j]
        c += 1
    return 'Possible'

print(f())

Submission status: Wrong Answer

Solution code:
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 a[0] < 2:
        return 'Impossible'
    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'
        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'
            c = 0
            t = a[j]
        c += 1
    return 'Possible'

print(f())

Submission status: Wrong Answer

Solution code:
import random
print(random.choice(['Possible','Impossible']))

Submission status: Wrong Answer

Solution code:
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'
        i = 2
    else:
        if a[-1] // 2 != a[0]:
            return 'Impossible'
    c = 2
    t = -1
    for j in range(i,n):
        if t != a[j]:
            if c < 2:
                return 'Impossible'
            c = 0
            t = a[j]
        c += 1
    return 'Possible'

print(f())

Submission status: Wrong Answer

Solution code:
#import string,itertools,fractions,heapq,re,array,bisect
#from math import *
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
    for i in range(m//2 + 1, m):
        if counts[i] < 2:
            good = False
    if good:
        print "Possible"
    else:
        print "Impossible"

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
# sys.setrecursionlimit(1000000)

# input aliases
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__":
    # main()
    solve()

Submission status: Accepted

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

Submission status: Accepted

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: Accepted

Solution code:
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')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

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

Submission status: Accepted

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

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

print("Possible")

Submission status: Accepted

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