human
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`.

Examples

Input

5
3 2 2 3 3

Output

Possible

Input

3
1 1 2

Output

Impossible

Input

10
1 2 2 2 2 2 2 2 2 2

Output

Possible

Input

10
1 1 2 2 2 2 2 2 2 2

Output

Impossible

Input

6
1 1 1 1 1 5

Output

Impossible

Input

5
4 3 2 3 4

Output

Possible
impor
assistant
#Here is Python code to determine whether such a tree exists.
t 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...