Problem Statement
You are attempting to develop a text editor for programmers.
Your editor consists of a line of semi-infinite length (there is a first position but no last position) and a cursor which points to the current character. The user can move the cursor one position to the left or right. If it is already in the leftmost position, it will not move.
Initially, the cursor is pointing at the leftmost character and all characters are ' '.
The user can write a lowercase latin letter or a bracket (either '(' or ')') to the current position of the cursor. This overwrites the letter currently there.
Your editor must check whether the line forms a valid text. A text s is considered valid if it satisfies any of these three conditions:
- it does not contain any brackets;
- the first character is '(', the last character is ')', and the characters between them form a valid text;
- it is a concatenation of two valid texts.
Thus, texts such as ((hello)(world)) are valid texts while texts such as okbu(ma)) are not. Take note that a valid text may contain spaces.
There are three commands that the user can give to your program. They are as follows:
- L - move the cursor one position to the left (if it is in the leftmost position, do not move it)
- R - move the cursor one position to the right
- any lowercase latin letter or a bracket - write the character to the current position of the cursor
After each command, your editor must determine two things:
- is the text in the editor a valid text?
- if so, what is the number of layers of nested brackets?
For example, the string ((()())()) is valid and has three layers of nested brackets.
Write a program to perform this task!
Input
The first line of input contains a single integer n (1 ≤ n ≤ 1000000), the number of commmands.
The next line of input contains a string of length n, where each character represents a command.
Output
In a single line print n integers, where the i-th integer is:
- -1 if the current text is not a valid text;
- the number of layers of nested brackets otherwise.
Subtasks
Subtask 1 (40%): n ≤ 3000
Subtask 2 (60%): No additional constraints.
Sample Input 1
11
(RaRbR)L)L(
Sample Output 1
-1 -1 -1 -1 -1 -1 1 1 -1 -1 2
Sample Input 2
11
(R)R(R)Ra)c
Sample Output 2
-1 -1 1 1 -1 -1 1 1 1 -1 1
Explanation
For Sample Input 1, _ denotes space, bold denotes cursor position.
- (__________
- (__________
- (a_________
- (a_________
- (ab________
- (ab________
- (ab)_______
- (ab)_______
- (a))_______
- (a))_______
- (())_______