「Wdoi-2」灵山之上神风起

题目背景

在天狗记者射命丸文的指(放)引(水)之下,灵梦一行人找到了山中的神社。 “在妖怪之山上还真的存在其他的神社啊。”灵梦感慨道。她们看到了由树木建造的神社正殿,以及正殿前的参拜道上的一排御柱,而更远处则是一片湖——风神之湖。湖面非常开阔,波光粼粼,一碧万顷,远处似乎有群山环抱,让人心旷神怡。 到达神社之时已经是傍晚了。正当灵梦和魔理沙感慨之时,见到在她们面前有一位白衣蓝裙的少女,东风谷早苗,拥有着引发奇迹程度的能力。为了找到守矢神社中的两位神灵,灵梦与魔理沙,向东风谷早苗产生了激烈的交战。 “那就在现人神的力量洗礼中思索吧!这召唤奇迹的神明之力!”

题目描述

### 简要题意 给定一个长度为 $n$ 的正整数序列 $a$ 满足对于所有 $i\in [1,n]$ 有 $a_i \in \{1,2,3\}$。 现在通过该序列构造一张含 $n$ 个节点,节点编号为 $1$ 到 $n$ 的图:对于数 $i$,如果 $a_i=1$,那么什么都不做;如果 $a_i=2$,那么向所有比 $i$ 小的数的节点连无向边;如果 $a_i=3$,那么向所有比 $i$ 大的数的节点连无向边。求出该图的最大独立集的大小。 最大独立集,指的是原图中一个点数尽量多的点集,这些点在原图中两两之间没有边**直接**相连。 ### 原始题意 然而,东风谷早苗(后称早苗)的弹幕密度相当之高,使人应接不暇,灵梦只得想个方法去减少她需要关注的弹幕数量。 数个回合过后,她发现,早苗每次释放弹幕只会释放出 $n$ 个弹幕,分别编号为 $1,2,\dots,n$,而她每释放一个弹幕,都会对应着产生一次神力波动。因而她的神力波动可以抽象为一个长度为 $n$ 的正整数数列 $\{a_n\}$。由于她的资历尚浅,只会使用三种神力,分别用 $1,2,3$ 表示,即 $\forall i \in [1,n]$,$a_i \in \{1,2,3\}$。 她发现,早苗的三种神力作用各不相同,具体而言如下: - 当 $a_i=1$ 时,她不会做任何事情。 - 当 $a_i=2$ 时,早苗会让第 $i$ 个弹幕向所有弹幕编号**小于** $i$ 的弹幕建立神力输送通道。 - 当 $a_i=3$ 时,早苗会让第 $i$ 个弹幕向所有弹幕编号**大于** $i$ 的弹幕建立神力输送通道。 接着,在各种神力的交互配合之下,密集的弹幕将展开于灵梦的眼前。而一旁的魔理沙发现,若是从这些弹幕中挑选出**尽可能多的**一群弹幕,使得每个弹幕之间不存在直接相连的神力输送通道,那么这群弹幕会产生【引发奇迹程度的能力】,是不必关注的。 由于【引发奇迹程度的能力】只能被触发**一次**,灵梦和魔理沙想要知道,**最多**有多少个弹幕是不必关注的。她们找到了你,希望你能帮她解答。

输入输出格式

输入格式


- 第一行,输入一个正整数 $n$,表示弹幕总数。 - 第二行,输入 $n$ 个正整数表示 $a_i$,具体含义见题目描述。

输出格式


- 共一行,输出一个正整数,表示**最多**有多少个弹幕是不必关注的。

输入输出样例

输入样例 #1

6
3 1 3 2 1 2

输出样例 #1

2

说明

### 样例解释 根据题意显然可以构造出如下的图。其中 $a_i=2$ 的用蓝色边表示,$a_i=3$ 的用红色边表示。 显然选取第 $2,3$ 个弹幕(已用绿色填图)是最多的情况。实际上对于这个样例,选取弹幕的方案不止一种,但是不存在更多的情况了。 ![](https://cdn.luogu.com.cn/upload/image_hosting/99a854cu.png) ### 数据范围 $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n\le} & \textbf{特殊性质} & \textbf{分值}\\\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}$$ - 特殊性质 $\text{A}$:所有的 $a_i=1$; - 特殊性质 $\text{B}$:所有的 $a_i$ 不是 $1$ 就是 $2$。 对于 $100\%$ 的数据,$1 \leq n \leq 10^5$,$a_i \in \{1,2,3\}$。