CF1479B1.Painting the Array I

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.

两个版本唯一的区别在于，本版本要求的是最大可能的答案。

霍默非常喜欢数组。今天，他正在用两种颜色（白色和黑色）给一个数组 $a_1, a_2, \dots, a_n$ 上色。对数组 $a_1, a_2, \dots, a_n$ 的一种上色方案由一个数组 $b_1, b_2, \dots, b_n$ 描述，其中 $b_i$ 表示 $a_i$ 的颜色（$0$ 表示白色，$1$ 表示黑色）。

根据上色方案 $b_1, b_2, \dots, b_n$，原数组 $a$ 被划分为两个新数组 $a^{(0)}$ 和 $a^{(1)}$：其中 $a^{(0)}$ 是 $a$ 中所有白色元素构成的子序列，$a^{(1)}$ 是 $a$ 中所有黑色元素构成的子序列。例如，若 $a = [1,2,3,4,5,6]$ 且 $b = [0,1,0,1,0,0]$，则 $a^{(0)} = [1,3,5,6]$，$a^{(1)} = [2,4]$。

一个数组 $c_1, c_2, \dots, c_k$ 的段数（记为 $\mathit{seg}(c)$）定义为：将 $c$ 中所有相邻且值相等的元素合并后，剩余元素的个数。例如，数组 $[1,1,2,2,3,3,3,2]$ 的段数为 $4$，因为合并相邻相同元素后得到 $[1,2,3,2]$。特别地，空数组的段数为 $0$。

霍默希望找到一个上色方案 $b$，使得 $a^{(0)}$ 和 $a^{(1)}$ 的段数之和（即 $\mathit{seg}(a^{(0)})+\mathit{seg}(a^{(1)})$）尽可能大。请找出这个最大值。

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$).

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 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]$ 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$.

在第一个例子中，我们可以选择 $a^{(0)} = [1,2,3,3]$、$a^{(1)} = [1,2,3]$，且 $\mathit{seg}(a^{(0)}) = \mathit{seg}(a^{(1)}) = 3$。因此答案为 $3+3 = 6$。

在第二个例子中，我们可以选择 $a^{(0)} = [1,2,3,4,5,6,7]$，而 $a^{(1)}$ 为空数组。可见 $\mathit{seg}(a^{(0)}) = 7$ 且 $\mathit{seg}(a^{(1)}) = 0$。因此答案为 $7+0 = 7$。