Vì có kết quả cao trong kỳ thi học sinh giỏi vừa qua nên Phát được mẹ thưởng cho một hộp màu tuyệt đẹp. Bộ màu ấy bao gồm \(n\) cây màu được xếp theo thứ tự từ trái qua phải, cây màu thứ \(i\) (\(1 \leq i \leq n\)) có màu được mô tả bởi một số nguyên \(a_i\).

Tuy nhiên, có một số sơ suất trong quá trình sản xuất nên hộp màu của Phát có thể chứa một số cây màu giống nhau. Vì là một người thích sự hoàn hảo nên Phát muốn bỏ bớt một số cây màu sao cho những cây màu còn lại đôi một phân biệt với nhau.

Để làm vậy, Phát sẽ chọn nhiều nhất một đoạn con gồm các cây màu liên tiếp rồi bỏ chúng đi, tức là, Phát sẽ chọn hai số nguyên \(l\) và \(r\) thoả mãn \(1 \leq l \leq r \leq n\) rồi bỏ các cây màu từ vị trí \(l\) đến vị trí \(r\) và giữ nguyên các cây màu còn lại.

Hãy giúp Phát tìm ra số lượng cây màu bị bỏ đi ít nhất sao cho các cây màu còn lại thoả mãn điều kiện.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \leq n \leq 10^6\)) là số lượng cây màu.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq n\)).

Output

• In ra một số nguyên duy nhất là số lượng cây màu bị bỏ đi.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 10^{2}\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 10^{3}\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \leq 10^{5}\).
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
1 1 2 2

2

5
1 4 1 4 5

2