CF1263E.Editor

The development of a text editor is a hard problem. You need to implement an extra module for brackets coloring in text.

Your editor consists of a line with infinite length and cursor, which points to the current character. Please note that it points to only one of the characters (and not between a pair of characters). Thus, it points to an index character. The user can move the cursor left or right one position. If the cursor is already at the first (leftmost) position, then it does not move left.

Initially, the cursor is in the first (leftmost) character.

Also, the user can write a letter or brackets (either (, or )) to the position that the cursor is currently pointing at. A new character always overwrites the old value at that position.

Your editor must check, whether the current line is the correct text. Text is correct if the brackets in them form the correct bracket sequence.

Formally, correct text (CT) must satisfy the following rules:

• any line without brackets is CT (the line can contain whitespaces);
• If the first character of the string — is (, the last — is ), and all the rest form a CT, then the whole line is a CT;
• two consecutively written CT is also CT.

Examples of correct texts: hello(codeforces), round, ((i)(write))edi(tor)s, ( me). Examples of incorrect texts: hello)oops(, round), ((me).

The user uses special commands to work with your editor. Each command has its symbol, which must be written to execute this command.

The correspondence of commands and characters is as follows:

• L — move the cursor one character to the left (remains in place if it already points to the first character);
• R — move the cursor one character to the right;
• any lowercase Latin letter or bracket (( or )) — write the entered character to the position where the cursor is now.

For a complete understanding, take a look at the first example and its illustrations in the note below.

You are given a string containing the characters that the user entered. For the brackets coloring module's work, after each command you need to:

• check if the current text in the editor is a correct text;
• if it is, print the least number of colors that required, to color all brackets.

If two pairs of brackets are nested (the first in the second or vice versa), then these pairs of brackets should be painted in different colors. If two pairs of brackets are not nested, then they can be painted in different or the same colors. For example, for the bracket sequence ()(())()() the least number of colors is $2$, and for the bracket sequence (()(()())())(()) — is $3$.

Write a program that prints the minimal number of colors after processing each command.

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

你的编辑器由一条无限长的行和一个光标组成，光标指向当前字符。请注意，光标仅指向某个字符（而非一对字符之间），即它指向某个索引位置上的字符。用户可以将光标向左或向右移动一个位置。若光标已位于第一个（最左侧）位置，则无法再向左移动。

初始时，光标位于第一个（最左侧）字符处。

此外，用户可在光标当前所指位置写入一个字母或括号（即 ( 或 )）。新字符总会覆盖该位置上原有的字符。

你的编辑器必须检查当前行是否为“正确文本”。当且仅当其中的括号构成一个正确的括号序列时，该文本才是“正确文本”。

形式化地，“正确文本”（CT）需满足以下规则：

• 任何不含括号的行均为 CT（该行可包含空格）；
• 若字符串首字符为 (、末字符为 )，且其余中间部分构成 CT，则整个字符串为 CT；
• 两个连续拼接的 CT 也构成 CT。

正确文本示例：hello(codeforces)、round、((i)(write))edi(tor)s、( me)。
错误文本示例：hello)oops(、round)、((me)。

用户通过特殊命令与你的编辑器交互。每个命令对应一个字符，输入该字符即可执行相应命令。

命令与字符的对应关系如下：

• L — 将光标向左移动一个字符（若光标已在第一个字符处，则保持不动）；
• R — 将光标向右移动一个字符；
• 任意小写拉丁字母或括号（( 或 )）— 将输入的字符写入光标当前位置。

为便于完全理解，请参阅下方注释中的第一个示例及其图示说明。

你将获得一个字符串，表示用户输入的一系列字符。为支持括号着色模块的功能，在执行每条命令后，你需要：

• 检查编辑器中当前文本是否为正确文本；
• 若是，则输出为所有括号着色所需的最少颜色数。

若两对括号存在嵌套关系（即一对括号完全包含在另一对之中，或反之），则这两对括号必须用不同颜色绘制；若两对括号互不嵌套，则它们可用相同或不同的颜色绘制。例如，对于括号序列 ()(())()()，最少颜色数为 $2$；而对于括号序列 (()(()())())(())，最少颜色数为 $3$。

请编写一个程序，在处理每条命令后输出所需的最少颜色数。

The first line contains an integer $n$ ($1 \le n \le 10^6$) — the number of commands.

The second line contains $s$ — a sequence of commands. The string $s$ consists of $n$ characters. It is guaranteed that all characters in a string are valid commands.

第一行包含一个整数 $n$（$1 \le n \le 10^6$）—— 表示命令的数量。

第二行包含字符串 $s$ —— 一串命令序列。字符串 $s$ 由 $n$ 个字符组成。保证字符串中的所有字符均为合法命令。

In a single line print $n$ integers, where the $i$-th number is:

• $-1$ if the line received after processing the first $i$ commands is not valid text,
• the minimal number of colors in the case of the correct text.

在一行中输出 $n$ 个整数，其中第 $i$ 个数为：

• 若处理前 $i$ 个命令后得到的字符串不是合法文本，则为 $-1$；
• 若为合法文本，则为所需颜色的最少数量。

In the first example, the text in the editor will take the following form:

1. (
   ^

2. (
   ^

3. (a
   ^

4. (a
   ^

5. (ab
   ^

6. (ab
   ^

7. (ab)
   ^

8. (ab)
   ^

9. (a))
   ^

10. (a))
    ^

11. (())
    ^

在第一个例子中，编辑器中的文本将呈现以下形式：

1. (
   ^

2. (
   ^

3. (a
   ^

4. (a
   ^

5. (ab
   ^

6. (ab
   ^

7. (ab)
   ^

8. (ab)
   ^

9. (a))
   ^

10. (a))
    ^

11. (())
    ^