시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 95 54 45 56.250%

문제

문자열 S의 i번째 접미사는 S의 i번째 글자에서 시작하는 접미사(Suffix)이다.

예를 들어, S = "abcde"인 경우에 0번째 접미사는 "abcde", 3번째 접미사는 "de" 이다.

S의 접미사 배열은 S의 모든 접미사를 사전 순으로 정렬한 배열이다. 이때, 배열에 들어있는 값은 접미사 번호이고, 정렬은 접미사 번호에 해당하는 접미사로 수행하게 된다.

예를 들어, S = "abca"인 경우에 접미사 배열은 (3, 0, 1, 2)가 된다.

길이가 N인 접미사 배열이 주어졌을 때, 그 접미사 배열을 만들 수 있는 S는 여러 가지가 있을 수 있다. 이때, S에 포함된 서로 다른 문자의 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 50)이 주어진다. 둘째 줄에는 접미사 배열의 결과가 주어진다.

출력

입력으로 주어진 접미사 배열을 만들 수 있는 S 중에서, S에 포함된 서로 다른 문자의 개수의 최솟값을 출력한다.

예제 입력 1

4
3 0 1 2

예제 출력 1

2

예제 입력 2

4
3 2 1 0

예제 출력 2

1

예제 입력 3

4
0 1 2 3

예제 출력 3

2

예제 입력 4

10
7 4 8 6 1 5 2 9 3 0

예제 출력 4

4

예제 입력 5

1
0

예제 출력 5

1

힌트

  • 예제 1: aaba
  • 예제 2: aaaa
  • 예제 3: aaab

 

출처