E. 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.

Input

The first line contains an integer n (1≤n≤106) — 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.

Output

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.

Examples

input
11
(RaRbR)L)L(
output
-1 -1 -1 -1 -1 -1 1 1 -1 -1 2
input
11
(R)R(R)Ra)c
output
-1 -1 1 1 -1 -1 1 1 1 -1 1

Note

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

(
^
(
^
(a
^
(a
^
(ab
^
(ab
^
(ab)
^
(ab)
^
(a))
^
(a))
^
(())
^

題意

題面很長(zhǎng)，但看note一眼就能看懂。

就給你了一個(gè)編輯器，LR表示左右光標(biāo)移動(dòng)，小寫字母和左右括號(hào)表示將光標(biāo)位置修改為左右括號(hào)和字母。（如果你現(xiàn)在就是最左邊，就不能往左邊移動(dòng)）

現(xiàn)在給你n次操作，讓你判斷是否為合法括號(hào)序列，如果合法輸出最大的括號(hào)嵌套數(shù)量，否則輸出-1

題解

視頻題解 https://www.bilibili.com/video/av77514280/

假設(shè)(是1，)是-1

我們維護(hù)前綴和，合法的括號(hào)序列是所有和為0，且前綴和的最小值大于等于0。如果滿足這個(gè)條件，俺么最大的括號(hào)嵌套數(shù)量就是前綴和的最大值。

這實(shí)際上可以用線段樹來做

代碼

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+107;
#define inf 0x3f3f3f3f


struct node{
	int l,r;//區(qū)間[l,r]
	int add;//區(qū)間的延時(shí)標(biāo)記
	int sum;//區(qū)間和
	int mx; //區(qū)間最大值
	int mn; //區(qū)間最小值
}tree[maxn*4+5];//一定要開到4倍多的空間

void pushup(int index){
	tree[index].sum = tree[index<<1].sum+tree[index<<1|1].sum;
	tree[index].mx = max(tree[index<<1].mx,tree[index<<1|1].mx);
	tree[index].mn = min(tree[index<<1].mn,tree[index<<1|1].mn);
}
void pushdown(int index){
	if(tree[index].add){

		tree[index<<1].sum += (tree[index<<1].r-tree[index<<1].l+1)*tree[index].add;
		tree[index<<1|1].sum +=(tree[index<<1|1].r-tree[index<<1|1].l+1)*tree[index].add;
		tree[index<<1].mx += tree[index].add;
		tree[index<<1|1].mx += tree[index].add;
		tree[index<<1].mn += tree[index].add;
		tree[index<<1|1].mn += tree[index].add;
		tree[index<<1].add += tree[index].add;
		tree[index<<1|1].add += tree[index].add;
		tree[index].add = 0;

	}
}
void build(int l,int r,int index){
	tree[index].l = l;
	tree[index].r = r;
	tree[index].add = 0;//剛開始一定要清0
	if(l == r){
		scanf("%d",&tree[index].sum);
		tree[index].mn = tree[index].mx = tree[index].sum;
		return ;
	}
	int mid = (l+r)>>1;
	build(l,mid,index<<1);
	build(mid+1,r,index<<1|1);
	pushup(index);
}
void updata(int l,int r,int index,int val){
	if(l <= tree[index].l && r >= tree[index].r){
		/*把原來的值替換成val,因?yàn)樵搮^(qū)間有tree[index].r-tree[index].l+1
		個(gè)數(shù)，所以區(qū)間和 以及 最值為：
		*/
		/*tree[index].sum = (tree[index].r-tree[index].l+1)*val;
		tree[index].mn = val;
		tree[index].mx = val;
		tree[index].add = val;//延時(shí)標(biāo)記*/
		//在原來的值的基礎(chǔ)上加上val,因?yàn)樵搮^(qū)間有tree[index].r-tree[index].l+1
		//個(gè)數(shù)，所以區(qū)間和 以及 最值為：
		tree[index].sum += (tree[index].r-tree[index].l+1)*val;
		tree[index].mn += val;
		tree[index].mx += val;
		tree[index].add += val;//延時(shí)標(biāo)記

		return ;
	}
	pushdown(index);
	int mid = (tree[index].l+tree[index].r)>>1;
	if(l <= mid){
		updata(l,r,index<<1,val);
	}
	if(r > mid){
		updata(l,r,index<<1|1,val);
	}
	pushup(index);
}
int querySum(int l,int r,int index){
	if(l <= tree[index].l && r >= tree[index].r){
		return tree[index].sum;
		//return tree[index].mn;
	}
	pushdown(index);
	int mid = (tree[index].l+tree[index].r)>>1;
	int ans = 0;
	int Max = 0;
	int Min = inf;
	if(l <= mid){
		ans += querySum(l,r,index<<1);
	}
	if(r > mid){
		ans += querySum(l,r,index<<1|1);
	}
	return ans;
}
int queryMi(int l,int r,int index){
	if(l <= tree[index].l && r >= tree[index].r){
		return tree[index].mn;
	}
	pushdown(index);
	int mid = (tree[index].l+tree[index].r)>>1;
	int ans = 0;
	int Max = 0;
	int Min = inf;
	if(l <= mid){
		Min = min(queryMi(l,r,index<<1),Min);
	}
	if(r > mid){
		Min = min(queryMi(l,r,index<<1|1),Min);
	}
	return Min;
}
int queryMx(int l,int r,int index){
	if(l <= tree[index].l && r >= tree[index].r){
		return tree[index].mx;
	}
	pushdown(index);
	int mid = (tree[index].l+tree[index].r)>>1;
	int ans = 0;
	int Max = 0;
	int Min = inf;
	if(l <= mid){
		Max = max(queryMx(l,r,index<<1),Max);
	}
	if(r > mid){
		Max = max(queryMx(l,r,index<<1|1),Max);
	}
	//return ans;
	return Max;
	//return Min;
}

string s;
int ss[maxn];
int main(){
	int n;
	scanf("%d",&n);n=n+5;
	build(1,n,1);
	cin>>s;
	int pos = 1;
	vector<int>ans;
	for(int i=0;i<s.size();i++){
		if(s[i]=='('){
			updata(pos,n,1,1-ss[pos]);
			ss[pos]=1;
		}else if(s[i]==')'){
			updata(pos,n,1,-1-ss[pos]);
			ss[pos]=-1;
		}else if(s[i]=='L'){
			if(pos>1)pos--;
			//pos=max(pos,1);
		}else if(s[i]=='R'){
			pos++;
		}else{
			if(ss[pos]==1){
				updata(pos,n,1,-1);
			}else if(ss[pos]==-1){
				updata(pos,n,1,1);
			}
			ss[pos]=0;
		}
		if(queryMi(1,n,1)==0&&querySum(n,n,1)==0){
			ans.push_back(queryMx(1,n,1));
		}else{
			ans.push_back(-1);
		}
	}
	for(int i=0;i<ans.size();i++){
		cout<<ans[i]<<" ";
	}
	cout<<endl;
}