文本编辑器的开发是一个难题。您需要实现一个额外的模块来为文本中的括号着色。
您的编辑器由无限长度的行和指向当前字符的光标组成。请注意,它仅指向一个字符(而不是一对字符之间)。因此,它指向一个索引字符。用户可以将光标向左或向右移动一个位置。如果光标已经位于第一个(最左边)位置,则它不会向左移动。
最初,光标位于第一个(最左边)字符。
此外,用户可以在光标当前指向的位置写入字母或括号(( 或 ))。新字符总是会覆盖该位置的旧值。
您的编辑器必须检查当前行是否是正确的文本。如果文本中的括号形成正确的括号序列,则文本是正确的。
从形式上来说,正确的文本 (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$$$ 个数字是:
- $$$-1$$$ 如果处理第一个 $$$i$$$ 命令后收到的行不是有效文本,
- 正确文本情况下的最小颜色数。
示例
输入 #1
11 (RaRbR)L)L(
输出 #1
-1 -1 -1 -1 -1 -1 1 1 -1 -1 2
输入 #2
11 (R)R(R)Ra)c
输出 #2
-1 -1 1 1 -1 -1 1 1 1 -1 1
注意
在第一个示例中,编辑器中的文本将采用以下形式:
1. (^
2. ( ^
3.(a ^
4.(a ^
5. (ab ^
6. (ab ^
7. (ab) ^
8.(ab)^
9. (a)) ^
10. (a)) ^
11. (()) ^