Painting the Array I

题面翻译

题意

本题与 CF1480D2 的唯一区别是本题询问最大可能解.

给定一个数组 $a$, 你将将 $a_i$ 染为 $b_i$ 色, 其中 $b$ 是由你指定的一个 01 数组. 将 $a$ 数组中被染成 0 色的数字取出来并依在 $a$ 中出现的顺序排列, 组成数组 $a^{(0)}$. 同理, 将 $a$ 数组中被染成 1 色的数字取出来并依在 $a$ 中出现的顺序排列, 组成数组 $a^{(1)}$. 我们定义 $seg(c)$ 是一个正整数, 其中 $c$ 是一个数组, $seg(c)$ 的值为在我们将 $c$ 中相邻的所有相同元素合并后, $c$ 数组的大小. 例如, $seg([1, 1, 4, 5, 1, 4]) = |[1, 4, 5, 1, 4]|=5$. 最大化 $seg(a^{(0)})+seg(a^{(1)})$.

输入格式

第一行包括一个正整数 $n(1\leq n\leq 10^5)$.

第二行包括 $n$ 个正整数 $a_1, a_2, \cdots,a_n(1\leq a_i\leq n)$.

输出格式

仅输出一个正整数, 代表最大的 $seg(a^{(0)})+seg(a^{(1)})$.

题目描述

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.

输入格式

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 a single integer, indicating the maximal possible total number of segments.

样例 #1

样例输入 #1

7
1 1 2 2 3 3 3

样例输出 #1

6

样例 #2

样例输入 #2

7
1 2 3 4 5 6 7

样例输出 #2

7

提示

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