Description

俄罗斯套娃由若干个从小到大的娃娃套成，一个完整的套娃包含大小从\(1\)到\(m\)的娃娃各一个，否则它是不完整的。
你可以把两个（可能不完整）的套娃合并为一个套娃，方法是拆开适当的几个娃娃后按从小到大的顺序重新套起来，需注意：
1.你只能把小娃娃套在大娃娃里面，不能出现相等大小。
2.你只能在合并两个套娃的时候拆开娃娃，拆开了就必须装回去，合并完只剩一个套娃。
3.一旦一个娃娃属于一个套娃，它就永远属于这个套娃，不能被取出，只能在合并的时候短暂被取出。
有\(n\)个娃娃排成一行，你只能合并相邻的套娃，求将所有娃娃套成若干个完整套娃（大小可能不同），所需拆开娃娃的最少次数。

Format

Input

每个测试点仅包含一组测试数据。
第一行一个整数\(n(1<=n<=500)\)。
接下来一行\(n\)个整数，表示每个套娃的大小，在\(1\)到\(500\)之间。

Output

输出最少的拆开次数，如果最终不能组成若干个完整套娃，输出"impossible"(不含引号)。

Sample 1

Input

7
1 2 3 2 4 1 3

Output

7

Sample 2

Input

7
1 2 1 2 4 3 3

Output

impossible

Limitation

3s, 1GB for each test case.

Subtasks

子任务1（25分）：\(n<=8\)。
子任务2（25分）：套娃大小不超过\(2\)。
子任务3（25分）：\(n<=50\)。
子任务4（25分）：无附加限制。

Source

Vijos Original