상자 빼내기

한 창고의 선반에는 상자가 왼쪽부터 오른쪽까지 한 줄로 놓여 있다. 상자는 모두 N개이고, 왼쪽부터 1번, 2번, 차례로 번호를 붙여 부른다. 상자마다 무게가 적혀 있다.

창고 관리자는 선반을 정리하려고 한다. 정리를 마친 선반은 왼쪽에서 오른쪽으로 갈수록 상자의 무게가 반드시 줄어들어야 한다. 앞쪽 상자가 뒤쪽 상자보다 가벼우면 안 되고, 무게가 같은 두 상자가 함께 남아 있어도 안 된다.

관리자가 쓸 수 있는 방법은 상자를 선반에서 빼내는 것 하나뿐이다. 남은 상자를 다른 자리로 옮기거나 순서를 바꿀 수는 없다. 상자를 빼내면 그 자리가 비고, 남은 상자들은 원래 놓인 순서를 그대로 지킨다.

선반에 남는 상자의 수가 가장 많아지도록 정리할 때, 빼내야 하는 상자의 최소 개수를 계산하는 프로그램을 작성하여라.

예를 들어 N=7개의 상자의 무게가 다음의 표와 같다고 해보자.

3번 상자와 6번 상자를 빼내면 선반에 남는 상자는 다음의 표와 같다.

왼쪽에서 오른쪽으로 갈수록 무게가 줄어들므로 정리 조건을 만족한다. 남은 상자는 5개이고 빼낸 상자는 2개다. 상자 1개만 빼내서 조건을 만족시키는 방법은 없으므로, 현재 예시에서의 정답은 2다.

3번 상자의 무게와 7번 상자의 무게는 둘 다 4라서 두 상자를 함께 남길 수는 없다. 이처럼 무게가 같은 상자가 섞여 있을 때는 그 가운데 한 개만 남을 수 있다.

남기는 상자를 다르게 고르고도 5개를 남길 수 있다. 예를 들어 3번과 7번을 빼내면 15, 11, 8, 5, 2가 남아 이쪽도 조건을 만족한다. 어느 쪽을 고르더라도 빼내는 상자가 2개라는 점은 같으므로 답은 달라지지 않는다.

처음부터 무게가 왼쪽에서 오른쪽으로 갈수록 줄어드는 경우도 있다. 이때는 상자를 하나도 빼낼 필요가 없다. 또한 상자가 1개뿐인 경우에도 조건을 따질 상대가 없으므로 빼낼 상자가 없다.

입출력 예시

예시 1

입력

7
15 11 4 8 5 2 4

출력

2

예시 2

입력

5
2407220 9506188 5579917 3823629 3963928

출력

2

예시 3

입력

1
356093

출력

0