# 合成大星星

- 参考时间限制：0.5 秒（参考环境：[评测环境与性能](../../../docs/评测环境与性能.md)；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：512 MB

## 背景故事

星星工坊有三种零件：左星壳 `<` 、右星壳 `>` 和发光的星屑 `*` . 一对方向正确的星壳可以把完成的图案包起来，做成更大的星星；完成的图案也可以并排拼接。星屑能让图案变长，却不妨碍星壳配对。

工坊的产品线很宽：只有星屑也能出厂，里面空空的一对星壳 `<>` 也算完成品。工坊主说，后者叫“留白款”。

工坊的传送带可以从左端或右端添零件。每添一次，工匠都想知道带上最长的一段完整星星图案有多长。

(本故事由GPT-6 Sol重写)

## 形式化问题描述

给定一个由 `<` 、`>` 、`*` 构成的序列。一个**合法片段**是它的一个非空连续子串，且删去所有 `*` 后得到合法的尖括号序列。空序列也视为合法，因此只含 `*` 的非空片段是合法的；`*` 的位置仍计入片段长度。

随后进行 $m$ 次操作，每次向当前序列的左端或右端加入一个标记。输出初始序列以及每次操作后的最长合法片段长度。若不存在合法片段，答案为 $0$ ；这也包括当前序列为空的情况。

合法的尖括号序列可以递归定义为：空序列合法；若 $A,B$ 合法，则 $AB$ 与 `<A>` 也合法。

## 输入格式

第一行两个整数 $n,m$ ，分别表示初始序列长度和操作次数。

接下来给出 $n$ 个以空白字符分隔的标记，顺序即初始序列。若 $n=0$ ，这一部分没有标记。

接下来 $m$ 行，每行给出一个整数 $p$ 和一个标记 $x$ . 当 $p=1$ 时在左端加入 $x$ ；当 $p=2$ 时在右端加入 $x$ .

## 输出格式

输出 $m+1$ 行。第一行是初始序列的答案；第 $i+1$ 行是第 $i$ 次操作后的答案。

## 样例 1

### 输入

```text
6 3
* < < < > >
2 >
1 >
1 <
```

### 输出

```text
4
7
7
9
```

### 解释

初始序列中最长的合法片段为 `<<>>` ，长度为 $4$ . 第一次操作后，整条序列 `*<<<>>>` 合法，长度为 $7$ . 第二次操作加在左端的 `>` 不能并入这个片段。第三次操作又在左端加上 `<` ，使整条长度为 $9$ 的序列合法。

## 样例 2

### 输入

```text
0 5
2 >
1 *
1 <
2 *
1 >
```

### 输出

```text
0
0
1
3
4
4
```

### 解释

初始序列为空，加入 `>` 后仍没有合法片段。之后的序列依次为 `*>` 、`<*>` 、`<*>*` 、`><*>*` ，最长合法片段长度依次为 $1,3,4,4$ .

## 数据范围与保证

- $0\le n,m\le 1\,000\,000$ .
- $p\in\{1,2\}$ ，$x$ 为 `<` 、`>` 或 `*` .

### 数据分组

| 分值比例 | 额外条件 |
| --- | --- |
| 20% | $n\le 25$ ，$m=0$ |
| 20% | $n\le 5\,000$ ，$m=0$ |
| 30% | $n,m\le 5\,000$ |
| 30% | 无额外条件 |