Painting the Array II

The only difference between the two versions is that this version asks the minimal possible answer.

Homer likes arrays a lot. Today he is painting an array $$$a_1, a_2, \dots, a_n$$$ with two kinds of colors, white and black. A painting assignment for $$$a_1, a_2, \dots, a_n$$$ is described by an array $$$b_1, b_2, \dots, b_n$$$ that $$$b_i$$$ indicates the color of $$$a_i$$$ ($$$0$$$ for white and $$$1$$$ for black).

According to a painting assignment $$$b_1, b_2, \dots, b_n$$$, the array $$$a$$$ is split into two new arrays $$$a^{(0)}$$$ and $$$a^{(1)}$$$, where $$$a^{(0)}$$$ is the sub-sequence of all white elements in $$$a$$$ and $$$a^{(1)}$$$ is the sub-sequence of all black elements in $$$a$$$. For example, if $$$a = [1,2,3,4,5,6]$$$ and $$$b = [0,1,0,1,0,0]$$$, then $$$a^{(0)} = [1,3,5,6]$$$ and $$$a^{(1)} = [2,4]$$$.

The number of segments in an array $$$c_1, c_2, \dots, c_k$$$, denoted $$$\mathit{seg}(c)$$$, is the number of elements if we merge all adjacent elements with the same value in $$$c$$$. For example, the number of segments in $$$[1,1,2,2,3,3,3,2]$$$ is $$$4$$$, because the array will become $$$[1,2,3,2]$$$ after merging adjacent elements with the same value. Especially, the number of segments in an empty array is $$$0$$$.

Homer wants to find a painting assignment $$$b$$$, according to which the number of segments in both $$$a^{(0)}$$$ and $$$a^{(1)}$$$, i.e. $$$\mathit{seg}(a^{(0)})+\mathit{seg}(a^{(1)})$$$, is as small as possible. Find this number.