Statement
길이 의 수열 가 주어진다.
당신은 다음 연산을 원하는 만큼 수행할 수 있다.
- 현재 수열에서 두 정수 을 고른다. 이때 이어야 하며, 현재 수열의 번째 원소부터 번째 원소까지가 모두 서로 다른 값이어야 한다.
- 조건을 만족한다면 이 구간을 수열에서 지운다. 지운 뒤에는 남은 원소들이 순서를 유지한 채 서로 붙는다.
최대한 적은 수의 원소를 남기려고 할 때, 남길 수 있는 원소 개수의 최솟값을 구하여라.
Input
입력은 다음과 같은 형식으로 주어진다.
Output
남길 수 있는 원소 개수의 최솟값을 출력한다.
Constraints
- .
- ().
- 입력으로 주어지는 모든 값은 정수이다.
Subtasks
Samples
예제 1
입력
5
1 2 1 2 3
출력
0
예를 들어 처음 두 원소 를 지우면 수열은 이 된다. 그 후 남은 세 원소는 모두 서로 다르므로 한 번에 지울 수 있다.
예제 2
입력
5
1 1 1 2 3
출력
1
예를 들어 세 번째 원소와 네 번째 원소를 지우고, 그 후 남은 을 지우면 원소 하나만 남길 수 있다.
예제 3
입력
4
7 7 7 7
출력
4
서로 다른 두 원소로 이루어진 구간조차 존재하지 않으므로 어떤 연산도 수행할 수 없다.