P8538 「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$ 的弹幕建立神力输送通道。 接着，在各种神力的交互配合之下，密集的弹幕将展开于灵梦的眼前。而一旁的魔理沙发现，若是从这些弹幕中挑选出**尽可能多的**一群弹幕，使得每个弹幕之间不存在直接相连的神力输送通道，那么这群弹幕会产生【引发奇迹程度的能力】，是不必关注的。 由于【引发奇迹程度的能力】只能被触发**一次**，灵梦和魔理沙想要知道，**最多**有多少个弹幕是不必关注的。她们找到了你，希望你能帮她解答。

无

无

### 样例解释 根据题意显然可以构造出如下的图。其中 $a_i=2$ 的用蓝色边表示，$a_i=3$ 的用红色边表示。 显然选取第 $2,3$ 个弹幕（已用绿色填图）是最多的情况。实际上对于这个样例，选取弹幕的方案不止一种，但是不存在更多的情况了。  ### 数据范围 $$ \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\}$。