非交叉的1212子序列¶

参考时间限制：0.5 秒；内存限制：2048 MiB。实际时限取目标环境中最慢正式文件的标程中位耗时乘2，再按0.5秒向上取整。见评测环境。

背景故事¶

信号员把两种脉冲记为1和2，想从一段记录中取出尽可能多组1212。用于标记1到2的配对线可以嵌套，但不能交叉。

(本故事由GPT-6重写)

给定长度为 \(n\) 、只含字符1与2的字符串 \(s\) ，选择尽可能多的子序列，使得：

每个子序列都恰好是1212，亦即选出 \(a<b<c<d\) ，满足 \(s_a=s_c=1\) 、\(s_b=s_d=2\) .
任意两个选出的子序列不使用同一个字符串位置。
对每个子序列标记两条配对线 \((a,b)\) 和 \((c,d)\) .任意两条来自不同子序列的配对线均不得交叉：不允许端点次序 \(u<x<v<y\) 或 \(x<u<y<v\) .

配对线可以嵌套，也可以互不相交。条件3只检查相邻的1到2配对，不检查子序列中间从2到1的连线。无需选择全部字符，空串的答案为零。

禁止交叉、允许嵌套的配对线

图只展示两条1到2配对线：左侧交叉不合法，右侧嵌套合法；它们不单独表示完整的1212子序列。

第一行整数 \(n\) ，第二行为字符串 \(s\) .当 \(n=0\) 时第二行为空。

输出一行整数，表示能选出的最大子序列数量。

16
1121122121222111

20
11221122111112222122

4
1122

\(0\le n\le10^7\) .字符串只含1和2。

分值比例	额外条件
100%	无额外条件

共有10个正式文件，每个10%。