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, \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 large as possible. Find this number.

Input

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$).

Output

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 $$$\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]$$$ and $$$a^{(1)}$$$ is empty. We can see that $$$\mathit{seg}(a^{(0)}) = 7$$$ and $$$\mathit{seg}(a^{(1)}) = 0$$$. So the answer is $$$7+0 = 7$$$.

Painting the Array I

Examples