P8538 "Wdoi-2" The Divine Wind Rises Above Mount Lingshan

Under the guidance (literally “leading by releasing water”) of the tengu reporter Shameimaru Aya, Reimu and her group found a shrine in the mountain. “There really is another shrine on Youkai Mountain.” Reimu sighed with emotion. They saw the main hall of the shrine built from trees, and a row of sacred pillars on the worship path in front of it. Farther away was a lake—the Lake of the Wind God. The lake surface was extremely wide, shimmering with waves, a vast expanse of green. In the distance, it seemed to be surrounded by mountains, making people feel refreshed and relaxed. When they arrived at the shrine, it was already evening. Just as Reimu and Marisa were marveling, they saw a girl in white clothes and a blue skirt standing before them: Kochiya Sanae, who possessed the ability to cause miracles. In order to find the two deities in Moriya Shrine, Reimu and Marisa engaged in a fierce battle with Kochiya Sanae. “Then, contemplate within the baptism of the living god’s power! This is the divine power that summons miracles!”

## 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.

- 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 one positive integer in a single line, indicating the **maximum** number of bullets that can be ignored.

## 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