合成大星星¶

参考时间限制：0.5 秒（参考环境：评测环境与性能；仅供预估）
实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 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\) 次操作后的答案。

6 3
* < < < > >
2 >
1 >
1 <

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

0 5
2 >
1 *
1 <
2 *
1 >

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