시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 70 24 16 34.043%

문제

러시아 전통 목제인형인 마트료시카는 그 안에 크기가 계속 작아지는 인형들이 들어있는 인형이다. 마트료시카를 열면 그 안에 더 작은 인형이 있고, 그 작은 인형의 안엔 또다시 작은 인형이 들어있고, 안에 더는 인형이 없을 때까지 계속 반복된다. 

최근 러시아 마트료시카 박물관은 개수만 다르고 비슷하게 생긴 마트료시카 세트들을 모아놓은 콜렉션을 전시했다. 그런데 그만부모의 통제에서 벗어난 난폭한 어린이들이 이 세트들을 모두 분리시켜 일렬로 세워버렸다. 박물관 알바생인 준빈이는 해고 당하지 않기 위해 어린이들이 일렬로 세워놓은 총 n개의 마트료시카를(인형들의 크기는 정수로 나타낼 수 있다고 가정하자), 원래 마트료시카 세트들이 몇 개였는지 세트별로 몇 개였는지 모르는 채로, 마트료시카 세트들로 재조립 해야 한다. 확실한 것은 모든 완전한 마트료시카 세트의 인형들의 크기들은 각각 크기가 1부터 어떤 수 m까지의 연속된 정수라는 것이다. 물론 m은 각 세트마다 다르다.

재조립 과정에서 준빈이는 다음의 규칙을 따라야한다.

  • 작은 인형 안에는 큰 인형이 들어갈 수 없다.
  • 두 그룹(부분적으로 재조립이 완료된 그룹)의 인형들을 합치려면 그 두 그룹이 (줄에서)서로 인접해 있어야 한다.
  • 인형이 한 번 그룹에 들어가면 다른 그룹과 합치는 작업을 할 때 외에는, 절대로 다른 그룹으로 옮기거나 아예 분리될 수 없다.

오래 걸리면 걸릴 수록 시급에서 까인다. 따라서 최대한 빨리 이 일을 마쳐야 한다. 복구할 때 인형을 열고 닫는 시간만 고려하자. 따라서 여는 횟수를 최소화하면 된다.  예를 들어보자. 그룹 [1, 2, 6]과 [4]를 합칠 때 여는 횟수의 최솟값은 2이다. 크기 6인 인형과 4인 인형을 열어야 하기 때문이다. 그룹 [1, 2, 5]와 [3, 4]를 합칠 때는 최소 횟수가 3이다.

분해된 마트료시카 세트들을 다시 합치는데 인형들을 최소 몇 번 열어야하는지 계산하자.

입력

첫번째 줄에는 일렬로 세워진 각 마트료시카 인형들의 개수 n(1 ≤ n ≤ 500)이 주어진다. 두번째 줄에는 각 마트료시카 인형의 크기(1 ≤ 크기 ≤ 500)가 줄에 세워진 순서대로 주어진다.

출력

마트료시카 세트들을 복구하기 위해 인형들을 여는 횟수의 최솟값을 출력한다. 만약 재조립이 불가능하다면(아이들이 훔쳤을 수도 있다) "impossible"을 출력한다.

예제 입력

7
1 2 3 2 4 1 3

예제 출력

7

힌트

출처

ACM-ICPC > World Finals > 2013 World Finals H번