1479B1 · Painting the Array I

Problem: 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 Format: 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 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 $\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$.