题目描述

Antonella has $N$ colored balls, and she wants to build a stable pile of balls with them. For a pile to be stable, every ball must either lie on the ground, or be placed exactly on top of two other balls. Also, balls lying on the ground must be tightly packed, which means that there should be no empty space between them. The picture below shows three arrangements of balls; the one on the left is a stable pile, while the other two are failed attempts.

:::align{center} :::

Antonella wants to build her stable pile in an incremental process. First, she will pick a ball and place it on the ground, forming a stable pile made of a single ball. Then, she will add the other $N-1$ balls to the pile, one at a time, keeping the pile stable at every step. If there are multiple places where Antonella could add a ball, she will choose the highest place (relative to the ground). If there are still multiple options, she can choose any of them.

A set of balls in a stable pile is considered connected if, for any two balls $s$ and $t$ in the set, there is a sequence of balls $s = b_0, b_1, \dots, b_k = t$ such that $b_{i-1}$ touches $b_i$ for $i=1, 2, \dots, k$. A cluster is a connected set of balls of the same color. The size of a cluster is the number of balls in it. The stable pile in the picture above has two red clusters of sizes $3$ and $1$, a green cluster of size $3$, and a blue cluster of size $6$.

Given the colors of the balls in the order in which Antonella will use them, you must tell the maximum size among all clusters of all possible stable piles that she can build.

输入格式

The first line contains an integer $N$ ($1 \le N \le 150$) indicating the number of balls.

The second line contains $N$ integers $K_1, K_2, \dots, K_N$ ($1 \le K_i \le 150$ for $i=1, 2, \dots, N$), where $K_i$ is the color of the $i$-th ball that Antonella will add to her pile.

输出格式

Output a single line with an integer indicating the maximum size among all clusters of all possible stable piles that Antonella can build.

3
1 2 1

2

3
1 1 1

3

4
1 5 5 1

2

6
1 2 2 1 2 3

3

提示

Explanation of Sample 1:

Antonella will place the first ball (color $1$) on the ground. She will place the second ball (color $2$) on the ground too, but it can be either on the left or on the right of the first ball. When inserting the third ball (color $1$), she will place it on top of the first two balls. Regardless of the choice Antonella makes for the second ball, she will get a stable pile with a cluster of size $2$ (color $1$) and a cluster of size $1$ (color $2$). Thus, the maximum size among all clusters of all possible stable piles is $2$.