# 非交叉的1212子序列

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

## 背景故事

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

(本故事由GPT-6重写)

## 形式化问题描述

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

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

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

![禁止交叉、允许嵌套的配对线](assets/example.svg)

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

## 输入格式

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

## 输出格式

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

## 样例 1

### 输入

```text
16
1121122121222111
```

### 输出

```text
2
```


## 样例 2

### 输入

```text
20
11221122111112222122
```

### 输出

```text
5
```


## 样例 3

### 输入

```text
0

```

### 输出

```text
0
```


## 样例 4

### 输入

```text
4
1122
```

### 输出

```text
0
```

## 数据范围与保证

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

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

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

[生成说明](tests/README.md)。