#163 diffdel

Loading problem...

Preparing the statement, recent submissions, and submit form.

#163 diffdel | DOJ

Authors: lunarlity

Statement

길이 $N$ 의 수열 $A$ 가 주어진다.

당신은 다음 연산을 원하는 만큼 수행할 수 있다.

현재 수열에서 두 정수 $l,r$ 을 고른다. 이때 $l<r$ 이어야 하며, 현재 수열의 $l$ 번째 원소부터 $r$ 번째 원소까지가 모두 서로 다른 값이어야 한다.
조건을 만족한다면 이 구간을 수열에서 지운다. 지운 뒤에는 남은 원소들이 순서를 유지한 채 서로 붙는다.

최대한 적은 수의 원소를 남기려고 할 때, 남길 수 있는 원소 개수의 최솟값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$N$ $A_1\ A_2\ \cdots\ A_N$

남길 수 있는 원소 개수의 최솟값을 출력한다.

Sample 1

Input

5
1 2 1 2 3

Output

예를 들어 처음 두 원소 $1,2$ 를 지우면 수열은 $1,2,3$ 이 된다. 그 후 남은 세 원소는 모두 서로 다르므로 한 번에 지울 수 있다.

Sample 2

Input

5
1 1 1 2 3

Output

예를 들어 세 번째 원소와 네 번째 원소를 지우고, 그 후 남은 $1,3$ 을 지우면 원소 하나만 남길 수 있다.

Sample 3

Input

4
7 7 7 7

Output

서로 다른 두 원소로 이루어진 구간조차 존재하지 않으므로 어떤 연산도 수행할 수 없다.