Trong một buổi sinh hoạt học thuật tại UMT, các thành viên được giao nhiệm vụ làm sạch một tập dữ liệu đầu vào bị trùng lặp. Mỗi bạn được cấp một dãy số gồm n phần tử nguyên, đại diện cho các mã sinh viên do hệ thống ghi nhận (nhưng đôi khi bị lỗi lặp mã).

Để chuẩn bị cho một buổi phân tích tiếp theo, cố vấn học thuật yêu cầu mỗi bạn phải làm sạch dãy mã sinh viên này sao cho mọi mã còn lại đều khác nhau (không có mã nào trùng lặp). Tuy nhiên, do hạn chế giao diện phần mềm, mỗi thao tác chỉ có thể là:

• Xóa mã đầu tiên trong danh sách.

• Xóa mã cuối cùng trong danh sách.

Nhiệm vụ của bạn là xác định số thao tác ít nhất cần thực hiện để danh sách chỉ còn các mã phân biệt.

Input

Dòng đầu tiên là một số nguyên n ~(1 ≤ n ≤ 10^5)~ — số lượng mã sinh viên được ghi nhận.

Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, . . . , a_n (1 ≤ a_i ≤ 10^5)~ — danh sách mã sinh viên.

Output

In ra một số nguyên duy nhất — số thao tác tối thiểu cần thực hiện để danh sách trở nên phân biệt.

Sample Input 1

4
4 3 3 2

Sample Ouput 1

2

Sample Input 2

5
1 2 3 4 5

Sample Ouput 2

0

Giải thích

Trong test mẫu trên, bạn có thể xóa hai phần tử đầu tiên để được dãy [3, 2], hoặc hai phần tử cuối cùng để được [4, 3]. Cả hai đều là dãy gồm các phần tử phân biệt, và cần đúng 2 thao tác.

Subtask:

• Subtask 1 (50% số điểm): ~n ≤ 5000~

• Subtask 2 (50% số điểm): Không giới hạn gì thêm.