Description

Brief Statement

You are given a positive integer sequence $a$ of length $n$, satisfying $a_i \in \{1,2,3\}$ for all $i \in [1,n]$.

Construct an undirected graph with $n$ nodes numbered from $1$ to $n$ using this sequence. For each $i$:

• If $a_i=1$, do nothing.
• If $a_i=2$, add undirected edges from node $i$ to all nodes with indices smaller than $i$.
• If $a_i=3$, add undirected edges from node $i$ to all nodes with indices greater than $i$.

Find the size of the maximum independent set of this graph.

A maximum independent set is a set of as many vertices as possible such that no two vertices in the set are directly connected by an edge in the original graph.

Original Statement

However, Kochiya Sanae (hereinafter referred to as Sanae) has an extremely high danmaku density, making it hard to keep up. Reimu had to find a way to reduce the amount of danmaku she needed to pay attention to.

After several rounds, she discovered that each time Sanae releases danmaku, she releases exactly $n$ bullets, numbered $1,2,\dots,n$. Each bullet she releases corresponds to a divine power fluctuation. Thus, her divine power fluctuations can be abstracted as a positive integer sequence of length $n$, $\{a_n\}$. Since she is still inexperienced, she can only use three kinds of divine power, represented by $1,2,3$. That is, $\forall i \in [1,n]$, $a_i \in \{1,2,3\}$.

She found that Sanae’s three kinds of divine power act differently, specifically:

• When $a_i=1$, she does nothing.
• When $a_i=2$, Sanae makes the $i$-th bullet establish divine power transfer channels to all bullets with indices smaller than $i$.
• When $a_i=3$, Sanae makes the $i$-th bullet establish divine power transfer channels to all bullets with indices greater than $i$.

Then, with various interactions and combinations of divine power, dense danmaku unfolds before Reimu’s eyes. Marisa, who is standing nearby, discovers that if they pick as many as possible bullets from these danmaku such that there is no directly connected divine power transfer channel between any pair of bullets, then this group of bullets will produce the “ability to cause miracles”, meaning they do not need to be paid attention to.

Since the “ability to cause miracles” can only be triggered once, Reimu and Marisa want to know: at most how many bullets can be ignored. They found you and hope you can help answer this question.

Input Format

• The first line contains a positive integer $n$, indicating the total number of bullets.
• The second line contains $n$ positive integers $a_i$. See the problem description for their meaning.

Output Format

• Output one positive integer in a single line, indicating the maximum number of bullets that can be ignored.

6
3 1 3 2 1 2

2

Hint

Sample Explanation

According to the statement, we can clearly construct the following graph. Edges for $a_i=2$ are shown in blue, and edges for $a_i=3$ are shown in red.

Obviously, choosing bullets $2,3$ (already filled in green) is the maximum. In fact, for this sample there is more than one valid selection plan, but there is no selection with more bullets.

Constraints

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n\le} & \textbf{Special Property} & \textbf{Score}\\\hline 1 & 10 & - & 20\\\hline 2 & 10^5 & \text{A} & 10\\\hline 3 & 10^5 & \text{B} & 30 \\\hline 4 & 10^5 & - & 40 \\\hline \end{array}$$

• Special Property $\text{A}$: all $a_i=1$.
• Special Property $\text{B}$: every $a_i$ is either $1$ or $2$.

For $100\%$ of the testdata, $1 \leq n \leq 10^5$, and $a_i \in \{1,2,3\}$.

Translated by ChatGPT 5