← 返回题目列表

Codeforces · 1479/B1

B1. 绘制阵列 I

中文机器翻译题面 查看原题

两个版本之间的唯一区别是该版本询问最大可能的答案。

Homer 非常喜欢数组。今天他正在用白色和黑色两种颜色绘制一个数组 $$$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$$$。

Homer 想要找到一个绘画作业 $$$b$$$,根据该作业,$$$a^{(0)}$$$ 和 $$$a^{(1)}$$$ 中的线段数尽可能大,即 $$$\mathit{seg}(a^{(0)})+\mathit{seg}(a^{(1)})$$$。找到这个号码。

输入

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

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$)。

输出

输出一个整数,表示最大可能的段总数。

示例

输入 #1

7
1 1 2 2 3 3 3

输出 #1

6

输入 #2

7
1 2 3 4 5 6 7

输出 #2

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