Đề bài có chút sửa đổi so với file PDF.

Matryoska là một bộ gồm những búp bê rỗng ruột có kích thước từ lớn đến nhỏ. Con búp bê nhỏ nhất sẽ được chứa đựng trong lòng con búp bê lớn hơn nó một chút, đến lượt mình con búp bê lớn được chứa trong một con búp bê khác lớn hơn, và cứ thế cho đến con lớn nhất sẽ chứa tất cả những con búp bê còn lại trong bộ. Một bộ ~m~ búp bê được gọi là đầy đủ nếu chứa tất cả các kích thước từ ~1~ đến ~m~. Có tất cả ~n~ búp bê được đặt thành hàng liên tiếp, cần kết hợp thành các bộ búp bê đầy đủ theo quy tắc:

• Có thể đặt bộ các con búp bê nhỏ bên trong một con búp bê lớn hơn.

• Có thể gộp kết hợp ~2~ bộ chỉ khi chúng được đặt kề nhau.

• Một búp bê ở trong một bộ không được phép chuyển sang bộ khác. Các búp bê trong ~1~ bộ chỉ được tách ra khi gộp kết hợp ~2~ bộ với nhau.

Khi kết hợp các bộ, ta cần mở (sau đó đóng) một số con và đặt bộ con nhỏ hơn vào bên trong. Ví dụ khi kết hợp ~2~ bộ ~[1,2,6]~ và ~[4]~ ta cần mở ~6~ và ~4~, đặt ~2~ (có chứa ~1~) vào trong ~4~, đặt ~4~ vào trong ~6~. Ta cần mở ~2~ lần. Khi kết hợp ~[1,3,5]~ và ~[2,4]~, ta cần ~4~ lần mở(đóng) búp bê ~2,3,4,5~.

Yêu cầu: Cho kích thước ~n~ búp bê theo thứ tự, xác định số lần mở (đóng) búp bê ít nhất để kết hợp được thành các bộ đầy đủ (kích thước các bộ có thể khác nhau).

Input

• Dòng đầu chứa số nguyên dương ~n~ ~(n \le 500)~

• Dòng thứ ~2~ chứ ~n~ số nguyên là kích thước ~n~ búp bê theo thứ tự trong hàng.

Output

Ghi ra số lần mở (đóng) ít nhất tìm được. Nếu không tìm được cách kết hợp thành các bộ đầy đủ, đưa ra Impossible.

Scoring

Sample Input 1

7
1 2 1 2 4 3 3

Sample Output 1

impossible

Sample Input 2

7
1 2 3 2 4 1 3

Sample Output 2

7