← 返回题目列表

Codeforces · 1394/E

E. 波博尼乌和钞票收藏

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

无论遇到什么困难,都不要害怕,微笑面对。

我又赚了十亿美元!

— 博博尼乌

Boboniu发行了他的货币,名为Bobo Yuan。波波元(BBY)是一系列货币。 Boboniu给它们每个人赋予了一个正整数标识符,例如BBY-1、BBY-2等。

Boboniu 有一个 BBY 系列。他的收藏看起来像一个序列。例如:

我们可以使用长度$$$n=9$$$的序列$$$a=[1,2,3,3,2,1,4,4,1]$$$来表示它。

现在 Boboniu 想要折叠他的收藏。您可以想象 Boboniu 将他的收藏贴在一张长纸上,然后将其折叠在货币之间:

Boboniu 只会将相同标识符的货币折叠在一起。换句话说,如果 $$$a_i$$$ 折叠在 $$$a_j$$$ ($$$1\le i,j\le n$$$) 上,则 $$$a_i=a_j$$$ 必须成立。 Boboniu并不关心你在折叠的过程中是否遵循这个规则。但一旦完成,就应该遵守规则。

折叠的正式定义在注释中描述。

根据上图,可以将$$$a$$$折叠两次。事实上,你最多可以折叠 $$$a=[1,2,3,3,2,1,4,4,1]$$$ 两次。所以它的最大折叠次数是$$$2$$$。

作为 Boboniu 的国际粉丝,您需要计算最大折叠次数。

给定一个长度为$$$n$$$的序列$$$a$$$,对于每个$$$i$$$ ($$$1\le i\le n$$$),你需要计算$$$[a_1,a_2,\ldots,a_i]$$$的最大折叠次数。

输入

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

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

输出

打印 $$$n$$$ 整数。其中第 $$$i$$$ 应等于 $$$[a_1,a_2,\ldots,a_i]$$$ 的最大折叠数。

示例

输入 #1

9
1 2 3 3 2 1 4 4 1

输出 #1

0 0 0 1 1 1 1 2 2

输入 #2

9
1 2 2 2 2 1 1 2 2

输出 #2

0 0 1 2 3 3 4 4 5

输入 #3

15
1 2 3 4 5 5 4 3 2 2 3 4 4 3 6

输出 #3

0 0 0 0 0 1 1 1 1 2 2 2 3 3 0

输入#4

50
1 2 4 6 6 4 2 1 3 5 5 3 1 2 4 4 2 1 3 3 1 2 2 1 1 1 2 4 6 6 4 2 1 3 5 5 3 1 2 4 4 2 1 3 3 1 2 2 1 1

输出#4

0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 3 3 3 3 4 4 4 5 5 6 7 3 3 3 4 4 4 4 3 3 4 4 4 4 4 5 5 5 5 6 6 6 7 7 8

注意

正式地,对于长度为 $$$n$$$ 的序列 $$$a$$$,让我们将折叠序列定义为长度为 $$$n$$$ 的序列 $$$b$$$,这样:

- $$$b_i$$$ ($$$1\le i\le n$$$) 是 $$$1$$$ 或 $$$-1$$$。
- 让$$$p(i)=[b_i=1]+\sum_{j=1}^{i-1}b_j$$$。对于所有 $$$1\le i<j\le n$$$,如果 $$$p(i)=p(j)$$$,则 $$$a_i$$$ 应等于 $$$a_j$$$。

($$$[A]$$$ 是布尔表达式 $$$A$$$ 的值。即,如果 $$$A$$$ 为 true,则 $$$[A]=1$$$,否则 $$$[A]=0$$$)。

现在我们将 $$$b$$$ 的折叠次数定义为 $$$f(b)=\sum_{i=1}^{n-1}[b_i\ne b_{i+1}]$$$。

$$$a$$$ 的最大折叠次数为 $$$F(a)=\max\{ f(b)\mid b \text{ 是 }a \}$$$ 的折叠序列。