write a go solution for Description:
The only difference between the two versions is that this version asks the maximal possible answer.

Homer likes arrays a lot. Today he is painting an array a_1,a_2,...,a_n with two kinds of colors, white and black. A painting assignment for a_1,a_2,...,a_n is described by an array b_1,b_2,...,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,...,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,...,c_k, denoted mathitseg(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. mathitseg(a^(0))+mathitseg(a^(1)), is as large as possible. Find this number.

Input Format:
The first line contains an integer n (1<=n<=10^5).

The second line contains n integers a_1,a_2,...,a_n (1<=qa_i<=qn).

Output Format:
Output a single integer, indicating the maximal possible total number of segments.

Note:
In the first example, we can choose a^(0)=[1,2,3,3], a^(1)=[1,2,3] and mathitseg(a^(0))=mathitseg(a^(1))=3. So the answer is 3+3=6.

In the second example, we can choose a^(0)=[1,2,3,4,5,6,7] and a^(1) is empty. We can see that mathitseg(a^(0))=7 and mathitseg(a^(1))=0. So the answer is 7+0=7.. Output only the code with no comments, explanation, or additional text.