CF1394E.Boboniu and Banknote Collection

No matter what trouble you're in, don't be afraid, but face it with a smile.

I've made another billion dollars!

— Boboniu

Boboniu has issued his currencies, named Bobo Yuan. Bobo Yuan (BBY) is a series of currencies. Boboniu gives each of them a positive integer identifier, such as BBY-1, BBY-2, etc.

Boboniu has a BBY collection. His collection looks like a sequence. For example:

We can use sequence $a=[1,2,3,3,2,1,4,4,1]$ of length $n=9$ to denote it.

Now Boboniu wants to fold his collection. You can imagine that Boboniu stick his collection to a long piece of paper and fold it between currencies:

Boboniu will only fold the same identifier of currencies together. In other words, if $a_i$ is folded over $a_j$ ($1\le i,j\le n$), then $a_i=a_j$ must hold. Boboniu doesn't care if you follow this rule in the process of folding. But once it is finished, the rule should be obeyed.

A formal definition of fold is described in notes.

According to the picture above, you can fold $a$ two times. In fact, you can fold $a=[1,2,3,3,2,1,4,4,1]$ at most two times. So the maximum number of folds of it is $2$.

As an international fan of Boboniu, you're asked to calculate the maximum number of folds.

You're given a sequence $a$ of length $n$, for each $i$ ($1\le i\le n$), you need to calculate the maximum number of folds of $[a_1,a_2,\ldots,a_i]$.

无论你遇到什么困难，都不要害怕，而要微笑着面对它。

我又赚了十亿美元！

——Boboniu

Boboniu 发行了自己的货币，名为“波波元”（Bobo Yuan，简称 BBY）。波波元是一系列货币，Boboniu 为每种货币赋予一个正整数标识符，例如 BBY-1、BBY-2 等。

Boboniu 拥有一套波波元收藏。他的收藏可视为一个序列。例如：

我们可以用长度为 $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]$ 的最大折叠次数。

The first line contains an integer $n$ ($1\le n\le 10^5$).

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le n$).

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

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le n$）。

Print $n$ integers. The $i$-th of them should be equal to the maximum number of folds of $[a_1,a_2,\ldots,a_i]$.

输出 $n$ 个整数。其中第 $i$ 个整数应等于子数组 $[a_1,a_2,\ldots,a_i]$ 的最大折叠次数。

Formally, for a sequence $a$ of length $n$, let's define the folding sequence as a sequence $b$ of length $n$ such that:

• $b_i$ ($1\le i\le n$) is either $1$ or $-1$.
• Let $p(i)=[b_i=1]+\sum_{j=1}^{i-1}b_j$. For all $1\le i \lt j\le n$, if $p(i)=p(j)$, then $a_i$ should be equal to $a_j$.

($[A]$ is the value of boolean expression $A$. i. e. $[A]=1$ if $A$ is true, else $[A]=0$).

Now we define the number of folds of $b$ as $f(b)=\sum_{i=1}^{n-1}[b_i\ne b_{i+1}]$.

The maximum number of folds of $a$ is $F(a)=\max{ f(b)\mid b \text{ is a folding sequence of }a }$.

形式化地，对于一个长度为 $n$ 的序列 $a$，我们定义其折叠序列为一个长度为 $n$ 的序列 $b$，满足以下条件：

• 对每个 $i$（$1\le i\le n$），$b_i$ 的值为 $1$ 或 $-1$；
• 定义 $p(i)=[b_i=1]+\sum_{j=1}^{i-1}b_j$。对任意 $1\le i \lt j\le n$，若 $p(i)=p(j)$，则必须有 $a_i = a_j$。

（其中 $[A]$ 表示布尔表达式 $A$ 的取值：当 $A$ 为真时 $[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 \text{ 的一个折叠序列} }$。