Tô màu mảng II

Cho một mảng $a_1,a_2,\dots ,a_n$. Ta tô màu mỗi phần tử bằng một trong hai màu: trắng hoặc đen. Sau khi tô, mảng $a$ được tách thành hai mảng con:

• $a^{(0)}$ gồm tất cả phần tử màu trắng, giữ nguyên thứ tự xuất hiện trong $a$;
• $a^{(1)}$ gồm tất cả phần tử màu đen, giữ nguyên thứ tự xuất hiện trong $a$.

Với một mảng $c_1,c_2,\dots ,c_k$, gọi $\text{seg}(c)$ là số đoạn thu được sau khi gộp mọi phần tử bằng nhau nằm liền kề nhau thành một. Ví dụ, $\text{seg}([1,1,2,2,3,3,3,2])=4$ vì mảng trở thành $[1,2,3,2]$. Quy ước số đoạn của mảng rỗng bằng $0$.

Hãy chọn cách tô màu sao cho $\text{seg}(a^{(0)})+\text{seg}(a^{(1)})$ nhỏ nhất, và in ra giá trị nhỏ nhất đó.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

• In ra một số nguyên duy nhất: tổng số đoạn nhỏ nhất có thể đạt được.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le a_i\le n$

Ví dụ