Cho một mảng ~a~ gồm ~n~ phần tử. Một đoạn con của mảng ~a~ là một đoạn các phẩn tử liên tiếp trong mảng ban đầu, giả sử ~a = [1, 2, 3, 4, 5, 6]~ thì một đoạn con của ~a~ có thể là ~[2, 3, 4]~.

Một đoạn con độc đáo của ~a~ là đoạn con của ~a~ trong đó tồn tại ít nhất một phần tử chỉ xuất hiện đúng một lần trong đoạn con đó.

Bạn được thực hiện thao tác sau nhiều lần hoặc không thực hiện: chọn một phần tử trong ~a~ và thay thế nó bằng một giá trị bất kì.

Yêu cầu: Hãy tính số thao tác cần thực hiện ít nhất để mọi đoạn con của ~a~ đều là đoạn con độc đáo.

Dữ liệu vào

• Dòng đầu tiên chứ số nguyên dương ~n~ ~(1 \le n \le 2 \times 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le n)~.

Kết quả ra

• Một số nguyên duy nhất là số thao tác ít nhất cần thực hiện để mọi đoạn con của ~a~ đều là đoạn con độc đáo.

Ràng buộc

• Có ~20\%~ số test có ~a_1 = a_2 = a_3 = \dots = a_n~.
• Có ~40\%~ số test có ~1 \le n \le 10^4~.
• Còn lại ~40\%~ số test không có giới hạn gì thêm.

Ví dụ

Dữ liệu vào

7
1 5 1 5 4 4 4 

Kết quả ra

2

Giải thích

Ta cần thay thế phần tử thứ 4 (hoặc thứ 3) và thứ 6, dãy ~a~ sau khi thay thế có thể là: 1 5 1 8 4 9 4