← 返回题目列表

AtCoder · agc005_c

C. 树木恢复

中文机器翻译题面 查看原题

分数: 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