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
Solve the task in PYTHON3.

=====
What is a Python code to determine whether such a tree exists?
assistant
#Here is Python code to determine whether such a tree exists.

#!/usr/bin/env python3
import sys

YES = "Possible"  # type: str
NO = "Impossible"  # type: str

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

# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()