CF1263E Editor

开发一个文本编辑器是一个难题。你需要为文本编辑器实现一个括号着色的附加模块。 你的编辑器由一行无限长度的文本和一个光标组成，光标指向当前字符。请注意，光标只指向某个字符（而不是字符之间的空隙）。因此，它指向一个字符的下标。用户可以将光标向左或向右移动一个位置。如果光标已经在第一个（最左侧）位置，则不会再向左移动。 初始时，光标位于第一个（最左侧）字符。 此外，用户可以在光标当前指向的位置写入一个字母或括号（即 ( 或 )）。新写入的字符总是会覆盖该位置原有的字符。 你的编辑器必须检查当前这一行是否为正确的文本。如果其中的括号构成了正确的括号序列，则认为文本是正确的。 形式化地说，正确的文本（CT）需要满足以下规则： - 任何没有括号的行都是 CT（该行可以包含空格）； - 如果字符串的第一个字符是 (，最后一个字符是 )，且中间的所有字符构成 CT，则整个字符串是 CT； - 两个连续写成的 CT 也是 CT。 正确文本的示例：hello(codeforces)、round、((i)(write))edi(tor)s、( me)。错误文本的示例：hello)oops(、round)、((me)。 用户通过特殊命令操作编辑器。每个命令都有其对应的符号，写入该符号即可执行相应命令。 命令与字符的对应关系如下： - L —— 光标向左移动一个字符（如果已经在第一个字符，则不移动）； - R —— 光标向右移动一个字符； - 任意小写拉丁字母或括号（( 或 )）—— 在光标当前位置写入该字符。 为了更好地理解，请参考第一个样例及其下方的说明。 给定一个包含用户输入的字符的字符串。对于括号着色模块的工作，在每条命令执行后，你需要： - 检查编辑器中的当前文本是否为正确文本； - 如果是，输出为所有括号着色所需的最少颜色数。 如果两个括号对是嵌套关系（一个在另一个内部或反之），则这两个括号对必须涂成不同的颜色。如果两个括号对不是嵌套关系，则它们可以涂成相同或不同的颜色。例如，对于括号序列 ()(())()()，最少需要 $2$ 种颜色；对于括号序列 (()(()())())(())，最少需要 $3$ 种颜色。 编写一个程序，在处理每条命令后，输出最少颜色数。

第一行包含一个整数 $n$（$1 \le n \le 10^6$）—— 命令的数量。 第二行包含 $s$——命令序列。字符串 $s$ 由 $n$ 个字符组成。保证字符串中的所有字符都是有效命令。

输出一行共 $n$ 个整数，第 $i$ 个数表示： - 如果处理完前 $i$ 条命令后得到的文本不是正确文本，则输出 $-1$； - 如果是正确文本，则输出最少需要的颜色数。

在第一个样例中，编辑器中的文本将依次变为： 1. ``` ( ^ ``` 2. ``` ( ^ ``` 3. ``` (a ^ ``` 4. ``` (a ^ ``` 5. ``` (ab ^ ``` 6. ``` (ab ^ ``` 7. ``` (ab) ^ ``` 8. ``` (ab) ^ ``` 9. ``` (a)) ^ ``` 10. ``` (a)) ^ ``` 11. ``` (()) ^ ``` 由 ChatGPT 4.1 翻译