시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 19 8 6 37.500%

문제

문자열 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에 포함된 서로 다른 문자의 개수의 최소값을 출력한다.

예제 입력

4
3 0 1 2

예제 출력

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