B'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 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 large as possible. Find this number. The first line contains an integer n ( 1 <= q n <= q 10^5 ). The second line contains n integers a_1, a_2, ... , a_n ( 1 <= q a_i <= q n ). Output a single integer, indicating the maximal possible total number of segments. In the first example, we can choose a^{(0)} = [1,2,3,3] , a^{(1)} = [1,2,3] and mathit{seg}(a^{(0)}) = mathit{seg}(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]'...