UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3971. [WF2013]Матрёшка

统计 下载数据

Description

俄罗斯套娃是一些从外到里大小递减的传统的俄罗斯木头玩偶组成的。当你打开一个俄罗斯套娃时,里面就会露出一个同样的俄罗斯套娃,再打开,就会再露出一个,不断重复。
俄罗斯的俄罗斯套娃博物馆最近收藏了一些外形相似的俄罗斯套娃集,只是里面嵌套的玩偶数量不相等。不幸的是,有一群过分热情的(和明显无人监督的)孩子们拆了他们,并放在一行上。有n个玩偶在一上,每个都有一个整数的大小,你需要重新组装套娃集,你既不知道套娃集的数量,也不知道某个套娃集内玩偶的数量,你只知道一个完好的套娃集内的玩偶大小是从1到某个数字m
在组装套娃集时,你必须遵守下列规则:
1.你只能将一个玩偶或者套娃集放入一个更大的玩偶中
2.你只能把相邻两个俄罗斯套娃组合在一起
3.已经被合并的玩偶是不能再重新拆出来的。
你的时间很宝贵,你只想尽快的组装好。唯一需要耗时的部分为打开一个玩偶并马上关上它。所以你要尽可能少的做这种操作。比如说:合并[1,2,6]与[4],你需要将大小为4和6的两个玩偶拆开。合并[1,2,5]与[3,4]代价为3。
求将n个玩偶重新拼成一些完好的俄罗斯套娃的最小代价。

Input

第一行一个数n,第二行包含n个数,依次表示每个玩偶的大小。

Output

如果答案存在,输出一个数表示将n个玩偶重新拼成一些完好的俄罗斯套娃的最小代价。否则输出“Impossible”

Sample Input

7
1 2 1 2 4 3 3

Sample Output

Impossible

Hint

1<=n<=500 , 1<=玩偶大小<=500



Source