주식회사 정올에서는 맥시마라고 불리는 새로운 정렬용 하드웨어를 개발하고자 한다. 맥시마란 n개 정수가 입력이 올 때 입력으로 들어온 수 중 가장 큰 숫자를 출력하는 기계이다.

맥시마는 여러 개의 정렬기를 조합해서 구현된다. 정렬기란 S(i, j)로 정의 되는 기계로 맥시마의 i번째 입력부터 j번째 입력까지(i ≤ j)를 숫자를 비-내림차순으로 정렬하고 나머지는 그대로 두어 새로운 입력을 말하는 부품을 말한다.

모든 정렬기를 거친 다음 n번째 입력에 있는 숫자가 맥시마의 출력이 된다.

만약 주어진 입력이 4 3 2 1 이고 S(2, 3), S(2, 4)라는 정렬기가 있을 경우 다음과 같은 형태로 맥시마가 구동 된다.

초기 : 4 3 2 1
S(2,3) 적용 : 4 2 3 1
S(2,4) 적용 : 4 1 2 3

이 경우는 맥시마가 3을 출력하게 된다.

당신은 몇 개의 정렬기를 없앨 경우에도 맥시마가 잘 동작함을 알 수 있었다. 여러 개의 정렬기가 주어졌을 때, 모든 가능한 입력에 대해서 올바른 출력을 내놓기 위해서 사용해야할 정렬기의 최소 개수를 찾는 프로그램을 작성하자.

정렬기의 순서는 반드시 지켜져야 한다. 편의상 맥시마에 들어오는 입력은 n개의 입력이 주어졌을 때 1부터 n까지의 정수가 들어온다고 가정 한다.

맥시마 timer 1s memory - MB

맥시마 1s - MB