KOI대학교 영재교육원에서 정보올림피아드에 관심 있는 학생들을 위한 캠프가 열린다.

캠프에 모인 학생들 중에는 원래부터 서로 아는 사이인 경우가 있다.

교육원에서는 다음과 같은 방식으로 학생들을 몇 개의 모둠으로 분할하려고 한다.

먼저 학생들의 명단을 생년월일 순서대로 나열한 다음, 나열된 순서에서 연속된 구간에 속한 학생들을 하나의 모둠으로 구성할 것이다.

이 때, 분할을 위한 원칙은 다음과 같다.

각 모둠에 속한 학생들은 서로 아는 사이여야 하고, 다른 모둠에 속한 학생들과는 서로 모르는 사이여야 한다.

그러나 위의 원칙으로 분할하는 것이 불가능한 경우가 많다.

그래서 가능한 위의 원칙을 따르는 방향으로 분할을 수행하기 위해, 분할 점수라는 값을 도입하여 구성된 분할이 얼마나 좋은지를 평가한다.

분할 점수는 다음과 같이 구해진다.

같은 모둠에 속한 학생들 중에서 서로 모르는 학생 쌍에 대해 각각 1점씩 점수를 부여하고,

다른 모둠에 속한 학생들 중에서 서로 아는 사이인 학생 쌍에 대해 각각 1점씩 점수를 부여한다.

다음 그림은 모둠의 수가 3이고 분할 점수가 5인 분할의 예를 보여준다.

그림에서 검은색 점은 학생을, 점 사이를 연결하는 선은 학생들이 서로 아는 사이임을 나타낸다.

점선으로 표시된 원은 모둠을 나타낸다.

학생들은 생년월일의 순서대로 1번부터 8번까지 번호로 표시되었고, 각 모둠은 A, B, C로 표시되어 있다.

이 예에서는 모둠 A와 모둠 B 사이의 점들을 연결하는 3개의 선이 존재하고,

모둠 B와 모둠 C 사이의 점들을 연결하는 1개의 선이 존재한다.

모둠 A와 모둠 B의 경우, 모둠 내의 모든 점들 쌍에 선이 존재하지만,

모둠 C에는 점 7과 점 8 사이에 선이 존재하지 않는다. 따라서 분할 점수는 3+1+1=5 이다.

아래 그림과 같이 두 개의 모둠으로 분할된 경우에도 분할 점수는 5이다.

아래 그림과 같이 4개의 모둠으로 분할된 경우에는 분할 점수가 8이다.

학생들에 대한 정보가 주어질 때, 분할 점수가 최소가 되는 분할을 구하는 프로그램을 작성하시오.

단, 모둠이 한 개만 있는 분할도 존재할 수 있다.

실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.

모둠 timer 1초 memory 256MB

모둠 1초 256MB