无论遇到什么困难,都不要害怕,微笑面对。
我又赚了十亿美元!
— 博博尼乌
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 \}$$$ 的折叠序列。