레이팅 미적용마트료시카는 크기가 점점 작아지는 인형들을 차례로 안에 넣는 러시아 전통 목각 인형 세트이다. 마트료시카 인형을 열면 안에서 같은 종류의 더 작은 인형이 나오고, 그 안에는 또 다른 인형이 있고, 이런 식으로 이어진다. 러시아 마트료시카 박물관은 최근 세트마다 들어 있는 인형 수만 다를 뿐 디자인이 비슷한 마트료시카 세트들의 소장품(c\(ol- le\)ction)을 전시했다. 안타깝게도(Unf\(or- tu\)nately) 지나치게 열성적인(ov\(er-ze\)alous) (그리고 명백히 감독받지 않은) 아이들이 이 세트들을 분리해 모든 인형을 한 줄로 늘어놓았다. 줄에는 \(n\)개의 인형이 있고 각 인형의 크기는 정수이다. 세트의 수도, 각 세트의 인형 수도 모르는 채로 마트료시카 세트들을 다시 조립해야 한다. 아는 것은 완전한 세트마다 인형 크기가 1부터 어떤 수 \(m\)까지 연속한다는 것뿐이며, 이 수는 세트마다 다를 수 있다. 세트를 다시 조립할 때 다음 규칙을 따라야 한다.
-
인형 하나 또는 중첩된 인형 묶음은 더 큰 인형 안에만 넣을 수 있다.
-
줄에서 인접한 두 인형 묶음만 합칠 수 있다.
-
인형이 일단 어떤 묶음의 일원이 되면 다른 묶음으로 옮기거나 묶음에서 영구히(p\(er- ma\)nently) 분리할 수 없다. 두 묶음을 합칠 때에만 일시적으로 분리할 수 있다. 당신의 시간은 소중하므로 이 재조립 과정을 가능한 한 빨리 끝내고 싶다. 이 작업에서 시간이 걸리는(ti\(me-co\)nsuming) 부분은 인형을 열었다가 다시 닫는 것뿐이므로, 이 횟수를 최소화하고 싶다. 예를 들어 묶음 [1, 2, 6]과 묶음 [4]를 합칠 때 최소 열기(및 닫기) 횟수는 2인데, 크기 6과 4인 인형을 열어야 하기 때문이다. 묶음 [1, 2, 5]와 묶음 [3, 4]를 합칠 때는 세 번 열어야 한다. 분해된 마트료시카 세트를 모두 합치는 데 필요한 최소 열기 횟수를 계산하는 프로그램을 작성하시오.
입력은 하나의 테스트 케이스로 이루어져 있다. 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 줄에 놓인 인형의 수를 나타내는 정수 \(n\) (\(1 \le n \le 500\))이 주어진다. 둘째 줄에는 줄에 나타나는 순서대로 인형들의 크기를 나타내는 \(n\)개의 양의 정수가 주어진다. 각 크기는 1 이상 500 이하이다.
마트료시카 세트를 다시 조립할 때 필요한 최소 열기 횟수를 출력한다. 재조립(reass\(em- bl\)ing)이 불가능하면(일부 아이가 과하게 열성적이어서 인형 몇 개를 가져갔을 수도 있다) impossible을 출력한다.
7
1 2 3 2 4 1 3
7
7
1 2 1 2 4 3 3
impossible