← 返回题目列表

Codeforces · 1263/E

E. 编辑

中文机器翻译题面 查看原题

文本编辑器的开发是一个难题。您需要实现一个额外的模块来为文本中的括号着色。

您的编辑器由无限长度的行和指向当前字符的光标组成。请注意,它仅指向一个字符(而不是一对字符之间)。因此,它指向一个索引字符。用户可以将光标向左或向右移动一个位置。如果光标已经位于第一个(最左边)位置,则它不会向左移动。

最初,光标位于第一个(最左边)字符。

此外,用户可以在光标当前指向的位置写入字母或括号(( 或 ))。新字符总是会覆盖该位置的旧值。

您的编辑器必须检查当前行是否是正确的文本。如果文本中的括号形成正确的括号序列,则文本是正确的。

从形式上来说,正确的文本 (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. (()) ^