分数: 700 点
问题陈述
Aoki 喜欢数字序列和树。
有一天,高桥给了他一个长度为整数的序列 N, a_1, a_2, ..., a_N,这让他想要构造一棵树。
青木想要构造一棵树 N 顶点编号 1 通过 N,这样对于每个 i = 1,2,...,N,顶点之间的距离 i 距离它最远的顶点是 a_i,假设每条边的长度为 1.
判断是否存在这样的树。
约束
- 2 ≦ N ≦ 100
- 1 ≦ a_i ≦ N-1
输入
输入由标准输入按以下格式给出:
N a_1 a_2 ... a_N
输出
如果存在满足条件的树,则打印 Possible。否则,打印 Impossible.
示例输入 1
5 3 2 2 3 3
示例输出 1
Possible

上图显示了满足条件的树的示例。红色箭头显示从每个顶点到距其最远顶点的路径。
示例输入 2
3 1 1 2
示例输出 2
Impossible
示例输入 3
10 1 2 2 2 2 2 2 2 2 2
示例输出 3
Possible
示例输入 4
10 1 1 2 2 2 2 2 2 2 2
示例输出 4
Impossible
示例输入 5
6 1 1 1 1 1 5
示例输出 5
Impossible
示例输入 6
5 4 3 2 3 4
示例输出 6
Possible