Zonal Computing Olympiad 2012, 26 Nov 2011

We consider sequences of opening and closing brackets with two types of brackets, () and [].  A bracket sequence is well-bracketed if we can pair up each opening bracket with a matching closing bracket in the usual sense.  For instance, the sequences (), [] ([]) and []([]) are well-bracketed, while (, ()], (], )( and [(]) are not well-bracketed.  In the last case, each opening bracket has a matching closing bracket and vice versa, but the intervals spanned by the different types of brackets intersect each other instead of being contained one within the other.

The alternating depth of a well-bracketed sequence tells us the maximum number of times we switch between the two types of brackets when we have inner matched brackets enclosed within outer matched brackets.  For instance, the alternating depth of (), [[[]]] and ()[][] is 1, the alternating depth of [()] and ()([]) is 2, the alternating depth of ([()]) and [()][(([]))] is 3, and so on.

Given a well-bracketed sequence, we are interested in computing three quantities.
- The alternating depth of the sequence.
- The maximum number of symbols between any pair of matched brackets of the type ( and ), including both the outer brackets.
- The maximum number of symbols between any pair of matched brackets of the type [ and ], including both the outer brackets.

For instance, the alternating depth of (([]))[[[()]]] is 2, the maximum number of symbols between a matched pair () is 6 and the maximum number of symbols between a matched pair [] is 8.



-----Input format-----
The input consists of two lines.  The first line is a single integer N, the length of the bracket sequence. Positions in the sequence are numbered 1,2,…,N. The second line is a sequence of N space-separated integers that encode the bracket expression as follows: 1 denotes an opening bracket (, 2 denotes a closing bracket ), 3 denotes an opening bracket [ and 4 denotes a closing bracket ].  Nothing other than 1, 2, 3 or 4 appears in the second line of input and the corresponding expression is guaranteed to be well-bracketed.

-----Output format-----
Your program should print 3 space-separated integers in a line, denoting the three quantities asked for in the following order: alternating depth, length of the maximum sequence between matching () brackets and length of the maximum sequence between matching [] brackets.  

-----Testdata-----
You may assume that 2 ≤ N ≤ 105.  In 30% of the test cases, 2 ≤ N ≤ 103.

- Subtask 1 (30 marks)
- Subtask 2 (70 marks)

-----Sample Input-----
14
1 1 3 4 2 2 3 3 3 1 2 4 4 4

-----Sample Output-----
2 6 8

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
n=int(input())
stringa=list(map(int,input().split()))
counter=0
counter1=0
counter3=0
somma1=0
somma2=0
massimo=0
massimo1=0
massimo3=0 
stack=[]
for par in stringa:
    if par==1 or par==3:
        if counter1==0 and par==1:
            counter1=1
            somma1=1
            massimo1=max(massimo1, 1)
        elif counter1>0:
            counter1+=1 
            somma1+=1
            massimo1=max(massimo1, somma1)
        if counter3==0 and par==3:
            counter3=1
            somma3=1
            massimo3=max(massimo3, 1)
        elif counter3>0:
            counter3+=1
            somma3+=1
            massimo3=max(massimo3, somma3)
        if counter==0:
            counter=1 
            massimo=max(massimo,1)
        if len(stack)>0 and par!=stack[-1]:
            counter+=1 
            massimo=max(massimo,counter)
        stack.append(par)
    else:
        if counter1>0:
            counter1-=1 
            somma1+=1
            massimo1=max(massimo1, somma1)
        if counter3>0:
            counter3-=1 
            somma3+=1
            massimo3=max(massimo3, somma3)
        appo=stack.pop()
        if len(stack)>0 and appo==stack[-1]:
            pass
        else:
            counter-=1
print(massimo, massimo1, massimo3)


# cook your dish here
class Stack:
	def __init__(self):
		self.items=[]
	
	def empty(self):
		return	self.items==[]
	
	def push(self,item):
		self.items.append(item)
	
	def pop(self):
		return self.items.pop()
	
	def top(self):
		return self.items[-1]
	
	def size(self):
		return len(self.items)
	def __iter__(self):
		return self
	def __next__(self):
		return _StackIterator(self.items())
		
class _StackIterator:
	def __init__(self,stack):
		self.stackRef=stack
		self.curInd=0
	def __iter__(self):
		return self
	def __next__(self):
		if self.curInd<self.size():
			entry=self.stackRef[self.curInd]
			self.curInd+=1
			return entry
		else:
			raise StopIteration
def main():
	
	n=int(input())
	Symbol=Stack()
	Index=Stack()
	FirstBracket=ThirdBracket=0
	arr=list(map(int,input().split()))
	
	for i in range(n):
		if arr[i]==1 or arr[i]==3:
			Symbol.push(arr[i])
			Index.push(i)
		else:
			temp=Symbol.pop()
			if temp==1:
				FirstBracket=max(FirstBracket,i-Index.pop()+1)
			elif temp==3:
				ThirdBracket=max(ThirdBracket,i-Index.pop()+1)
	seq=Stack()
	AlterDepth=0
	curDepth=Stack()
	for i in range(n):
		if (arr[i]==1 or arr[i]==3) and seq.empty():
			curDepth.push(1)
			seq.push(arr[i])
			AlterDepth=max(AlterDepth,curDepth.top())
			
		elif arr[i]==1 and seq.top()==3:
			curDepth.push(curDepth.top()+1)
			seq.push(arr[i])
			AlterDepth=max(AlterDepth,curDepth.top())
			
		elif arr[i]==3 and seq.top()==1:
			curDepth.push(curDepth.top()+1)
			seq.push(arr[i])
			AlterDepth=max(AlterDepth,curDepth.top())
		
		elif (arr[i]==1 or arr[i]==3):
			curDepth.push(curDepth.top())
			seq.push(arr[i])
			AlterDepth=max(curDepth.top(),AlterDepth)
		
		elif arr[i]==2 or arr[i]==4:
			curDepth.pop()
			seq.pop()
	print(AlterDepth,FirstBracket,ThirdBracket)
				
	
def __starting_point():
	
	main()
__starting_point()

class Stack:
	def __init__(self):
		self.items=[]
	
	def empty(self):
		return	self.items==[]
	
	def push(self,item):
		self.items.append(item)
	
	def pop(self):
		return self.items.pop()
	
	def top(self):
		return self.items[-1]
	
	def size(self):
		return len(self.items)
	def __iter__(self):
		return self
	def __next__(self):
		return _StackIterator(list(self.items()))
		
class _StackIterator:
	def __init__(self,stack):
		self.stackRef=stack
		self.curInd=0
	def __iter__(self):
		return self
	def __next__(self):
		if self.curInd<self.size():
			entry=self.stackRef[self.curInd]
			self.curInd+=1
			return entry
		else:
			raise StopIteration
def main():
	
	n=int(input())
	Symbol=Stack()
	Index=Stack()
	FirstBracket=ThirdBracket=0
	arr=list(map(int,input().split()))
	
	for i in range(n):
		if arr[i]==1 or arr[i]==3:
			Symbol.push(arr[i])
			Index.push(i)
		else:
			temp=Symbol.pop()
			if temp==1:
				FirstBracket=max(FirstBracket,i-Index.pop()+1)
			elif temp==3:
				ThirdBracket=max(ThirdBracket,i-Index.pop()+1)
	seq=Stack()
	AlterDepth=0
	curDepth=Stack()
	for i in range(n):
		if (arr[i]==1 or arr[i]==3) and seq.empty():
			curDepth.push(1)
			seq.push(arr[i])
			AlterDepth=max(AlterDepth,curDepth.top())
			
		elif arr[i]==1 and seq.top()==3:
			curDepth.push(curDepth.top()+1)
			seq.push(arr[i])
			AlterDepth=max(AlterDepth,curDepth.top())
			
		elif arr[i]==3 and seq.top()==1:
			curDepth.push(curDepth.top()+1)
			seq.push(arr[i])
			AlterDepth=max(AlterDepth,curDepth.top())
		
		elif (arr[i]==1 or arr[i]==3):
			curDepth.push(curDepth.top())
			seq.push(arr[i])
			AlterDepth=max(curDepth.top(),AlterDepth)
		
		elif arr[i]==2 or arr[i]==4:
			curDepth.pop()
			seq.pop()
	print(AlterDepth,FirstBracket,ThirdBracket)
				
	
def __starting_point():
	
	main()

__starting_point()

# cook your dish here
n=int(input())
arr=list(map(int,input().split()))
b1=b2=maxb1=maxb2=b1pos=b2pos=0
stacklen=0
stack=[]
currtoggle=0
maxtoggle=0
for i in range(n):
	if arr[i]==1:
		if b1==0:
			b1pos=i
		b1+=1
		if currtoggle==0 or stack[-1]==3:
			currtoggle+=1
		maxtoggle=max(currtoggle,maxtoggle)
		stack.append(1)
		stacklen+=1
	elif arr[i]==2:
		b1-=1
		if b1==0 and i-b1pos+1>maxb1:
			maxb1=i-b1pos+1
		stack.pop()
		stacklen-=1
		if stacklen==0 or stack[-1]==3:
			currtoggle-=1
	elif arr[i]==3:
		if b2==0:
			b2pos=i
		b2+=1
		if currtoggle==0 or stack[-1]==1:
			currtoggle+=1
		maxtoggle=max(currtoggle,maxtoggle)
		stack.append(3)
		stacklen+=1
	else:
		b2-=1
		if b2==0 and i-b2pos+1>maxb2:
			maxb2=i-b2pos+1
		stack.pop()
		stacklen-=1
		if stacklen==0 or stack[-1]==1:
			currtoggle-=1
print(maxtoggle,maxb1,maxb2)

n=int(input())
arr=list(map(int,input().split()))
b1=b2=maxb1=maxb2=b1pos=b2pos=0
stacklen=0
stack=[]
currtoggle=0
maxtoggle=0
for i in range(n):
	if arr[i]==1:
		if b1==0:
			b1pos=i
		b1+=1
		if currtoggle==0 or stack[-1]==3:
			currtoggle+=1
		maxtoggle=max(currtoggle,maxtoggle)
		stack.append(1)
		stacklen+=1
	elif arr[i]==2:
		b1-=1
		if b1==0 and i-b1pos+1>maxb1:
			maxb1=i-b1pos+1
		stack.pop()
		stacklen-=1
		if stacklen==0 or stack[-1]==3:
			currtoggle-=1
	elif arr[i]==3:
		if b2==0:
			b2pos=i
		b2+=1
		if currtoggle==0 or stack[-1]==1:
			currtoggle+=1
		maxtoggle=max(currtoggle,maxtoggle)
		stack.append(3)
		stacklen+=1
	else:
		b2-=1
		if b2==0 and i-b2pos+1>maxb2:
			maxb2=i-b2pos+1
		stack.pop()
		stacklen-=1
		if stacklen==0 or stack[-1]==1:
			currtoggle-=1
print(maxtoggle,maxb1,maxb2)


import collections


def convertInputToBrackets(arr):
    res = []

    for elem in arr:
        if elem == "1":
            res.append("(")
        elif elem == "2":
            res.append(")")
        elif elem == "3":
            res.append("[")
        elif elem == "4":
            res.append("]")

    return res


def solve(n, arr):
    balParanthesis, balBrackets = 0, 0
    balParans, balBracks = [0], [0]
    stack = []

    altDepth, maxAltDepth = 0, 0
    maxParanLength, maxBrackLength = 0, 0

    for ch in arr:
        if ch == ")" or ch == "]":
            if ch == ")":
                balParanthesis -= 1
            elif ch == "]":
                balBrackets -= 1

            lastCh, lastAltDepth = stack.pop()
            maxAltDepth = max(maxAltDepth, lastAltDepth)
        else:
            if ch == "(":
                balParanthesis += 1
            elif ch == "[":
                balBrackets += 1

            if not stack:
                stack.append((ch, 1))
            elif stack[-1][0] != ch:
                stack.append((ch, stack[-1][1] + 1))
            else:
                stack.append(stack[-1])

        balBracks.append(balBrackets)
        balParans.append(balParanthesis)

    lastParan, lastBrack = -1, -1

    for i in range(n+1):
        if balBracks[i] == 0:
            maxBrackLength = max(maxBrackLength, i-lastBrack)
            lastBrack = i

        if balParans[i] == 0:
            maxParanLength = max(maxParanLength, i - lastParan)
            lastParan = i

    return " ".join(map(str, (maxAltDepth, maxParanLength, maxBrackLength)))


n = int(input().strip())
arr = input().strip().split()
arr = convertInputToBrackets(arr)

print(solve(n, arr))


#dt = {} for i in x: dt[i] = dt.get(i,0)+1
#dt = {k:v for k,v in sorted(x.items(), key=lambda i: i[1])}
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]

n = inp()
x = ip()
brac,ind = [],[]
dt = {2:0,4:0}
for i in range(n):
    if x[i] in [1,3]:
        brac.append(x[i])
        ind.append(i)
        continue
    dt[x[i]] = max(dt[x[i]],i-ind[-1]+1)
    ind.pop()
    brac.pop()
alt = 0
brac,depth = [],[]
for i in range(n):
    if (x[i] == 1 or x[i] == 3) and brac == []:
        brac.append(x[i])
        depth.append(1)
        alt = max(alt,depth[-1])
    elif x[i]*brac[-1] == 3:
        brac.append(x[i])
        depth.append(depth[-1]+1)
        alt = max(alt,depth[-1])
    elif x[i]==1 or x[i]==3:
        brac.append(x[i])
        depth.append(depth[-1])
        alt = max(alt,depth[-1])
    elif x[i]==2 or x[i]==4:
        brac.pop()
        depth.pop()
    
print(alt,dt[2],dt[4])


t = int(input())

s = ""
g = []

g = list(map(int, input().split()))
for ele in g:
	if ele == 1:
		s += '('
	elif ele == 2:
		s += ')'
	elif ele == 3:
		s += '['
	else :
		s += ']'

#s = input()
#t = len(s)
stack = []
#print(s)
deptho = 0
if len(s) > 0:
	deptho = 1


d = {}
d[0]  = deptho
d[1]  = 0
d[2] = 0

#vis = [0]*n
stack = []
depth = []


for i in range(t):
	if len(stack) == 0 and (s[i] == '(' or s[i] == '['):
		stack.append(s[i])
		depth.append(1)
	elif (s[i] == '(' and stack[-1] == '[') or (s[i] == '[' and stack[-1] == '('):
		stack.append(s[i])
		depth.append(depth[-1]+1)
	elif (s[i] == '(') or (s[i] == '['):
		stack.append(s[i])
		depth.append(depth[-1])

	deptho = max(deptho, depth[-1])

	if s[i] == ')' or s[i] == ']':
		stack.pop()
		depth.pop()

d[0] = deptho


p_char = 0
sq_char = 0
max_sq_char = 0
max_p_char = 0
p_depth = 0
sq_depth = 0

for i in range(t):
	if(s[i] == '('):
		p_depth += 1
	if(s[i] == '['):
		sq_depth+=1

	if(p_depth):
		p_char+=1
	if(sq_depth):
		sq_char+=1

	max_sq_char = max(max_sq_char, sq_char)
	max_p_char = max(max_p_char, p_char)

	if(s[i] == ')'):
		p_depth-=1
	if(s[i] == ']'):
		sq_depth-=1

	if(p_depth == 0):	p_char = 0
	if(sq_depth == 0):	sq_char = 0

d[1] = max_p_char
d[2] = max_sq_char
print(d[0],d[1],d[2])





n=int(input())

a=[int(x) for x in input().split()]
k,d=0,0
st=[]

st.append(a[0])
k,d=1,1
for i in range(1,n):
    if a[i]==1 or a[i]==3:
        st.append(a[i])

        if st[len(st)-1]!=st[len(st)-2]:
            k+=1
            if k>d:
                d+=1
        #print(st,k,d)
    else:
        try:
            if st[len(st)-1]!=st[len(st)-2]:
                k-=1
            st.pop()
        except:
            st.pop()
            k-=1
        #print(st,k,d)

c1,max1=0,0
s1=[]
for i in range(n):
    try:
        if len(s1)==0 and a[i]==1:
            s1.append(a[i])
            c1+=1
        elif len(s1)!=0 and (a[i]==1 or a[i]==3):
            s1.append(a[i])
            c1+=1

        elif a[i]==2 or a[i]==4:
            s1.pop()
            c1+=1
        if max1 < c1:
            max1 = c1
        if len(s1)==0:
            c1=0
    except:
        pass



c2,max2=0,0
s2=[]
for i in range(n):
    try:
        if len(s2)==0 and a[i]==3:
            s2.append(a[i])
            c2+=1
        elif len(s2)!=0 and (a[i]==1 or a[i]==3):
            s2.append(a[i])
            c2+=1

        elif a[i]==2 or a[i]==4:
            s2.pop()
            c2+=1
        if max2 < c2:
            max2 = c2
        if len(s2)==0:
            c2=0
    except:
        pass

print(d,max1,max2)


n=int(input())
it=list(map(int,input().split()))
maa=0
ma=0
j=0
dd=0
ss={}
mi=0
a=[]
b=[]
for i in it:
    i-=1
    if i==1 or i==3:
        c=a.pop()
        d=b.pop()
        if i==1:
            maa=max(maa,j-c[1]+1)
        else:
            mi=max(mi,j-c[1]+1)
    else:
        if a==[]:
            a.append([i,j])
            b.append(1)
        else:
            
            if i==a[-1][0]:
                
                b.append(b[-1])
            else:
                b.append(b[-1]+1)
            a.append([i,j])
    if b:
        ma=max(ma,b[-1])
    j+=1
   # print(a,b)
    
print(ma,maa,mi)

        


length = int(input())
brackets = [int(i) for i in input().split()]
alternateDepths = []
squareSymbols, roundedSymbols = 0, 0

lastAlternatedLevel, lastAlternatedBracket, alDepth, level = [None], [None], 0, 0
lowestSquareHeight, lowestRoundedHeight = float("inf"), float("inf")
betweenSquare, betweenRounded = 0, 0
for i in brackets:
	if lowestRoundedHeight != float("inf"):
		betweenRounded += 1
	if lowestSquareHeight != float("inf"):
		betweenSquare += 1

	if i in [1, 3]:
		level += 1
		if i != lastAlternatedBracket[-1]:
			alDepth += 1
			lastAlternatedBracket.append(i)
			lastAlternatedLevel.append(level)
		if i == 1 and level < lowestRoundedHeight:
			# print("Setting Rounded", level)
			lowestRoundedHeight = level
			betweenRounded += 1
		elif i == 3 and level < lowestSquareHeight:
			lowestSquareHeight = level
			betweenSquare += 1
	else:
		if i == lastAlternatedBracket[-1] + 1 and level == lastAlternatedLevel[-1]:
			alternateDepths.append(alDepth)
			alDepth -= 1
			lastAlternatedLevel.pop()
			lastAlternatedBracket.pop()

		if i == 2 and level == lowestRoundedHeight:
			# print("here1", betweenRounded)
			if betweenRounded > roundedSymbols:
				roundedSymbols = betweenRounded
			lowestRoundedHeight = float("inf")
			betweenRounded = 0

		if i == 4 and level == lowestSquareHeight:
			if betweenSquare > squareSymbols:
				squareSymbols = betweenSquare
			lowestSquareHeight = float("inf")
			betweenSquare = 0

		level -= 1

print(max(alternateDepths), roundedSymbols, squareSymbols)


def solution(s, op, cl):
    if op not in s:
        return 0
    
    st = []
    le = mle = 0

    for c in s:
        if c == op:
            st.append(c)
        if c == cl:
            st.pop()

        le += 1

        if not st:
            if le > mle:
                mle = le

            le = 0

    return mle


def altdepth(s):
    pre = []
    dep = []
    ma = 0

    for c in s:
        if c == ')' or c == ']':
            pre.pop()
            dep.pop()
            continue

        if not pre:
            pre.append(c)
            dep.append(1)

        elif c != pre[-1]:
            pre.append(c)
            dep.append(dep[-1] + 1)

        else:
            pre.append(c)
            dep.append(dep[-1])

        if dep:
            ma = max(ma, dep[-1])

    return ma

n = int(input())
x = '()[]'
s = ''.join(x[i - 1] for i in list(map(int, input().split())))

print(altdepth(s), solution(s, '(', ')'), solution(s, '[', ']'))

# cook your dish here
n = int(input())
a = list(map(int,input().split()))
#a = [1,1,3,4,1,2,2,2]
#n = 14
k = 0
l = 0
ans1 = 0
ans2 = 0
b = 0
c = 0
mark1 = 0
mark2 = 0
for i in range(0,n):
  if a[i]==1 and mark1==0:
    b += 1
    k = i
    mark1=1
  elif a[i]==1:
    b += 1
  elif a[i]==2 and b==1:
    b -= 1
    k = i-k+1
    ans1 = max(ans1,k)
    mark1 = 0
  elif a[i]==2:
    b -= 1
  elif a[i]==3 and mark2==0:
    c += 1
    l = i
    mark2=1
  elif a[i]==3:
    c += 1
  elif a[i]==4 and c==1:
    c -= 1
    l = i-l+1
    ans2 = max(ans2,l)
    mark2 = 0
  elif a[i]==4:
    c -= 1
def alt_solve(s):
    pre = []
    dep = []
    ma = 0

    for c in s:
        if c == 2 or c == 4:
            pre.pop()
            dep.pop()
            continue

        if not pre:
            pre.append(c)
            dep.append(1)

        elif c != pre[-1]:
            pre.append(c)
            dep.append(dep[-1] + 1)

        else:
            pre.append(c)
            dep.append(dep[-1])

        if dep:
            ma = max(ma, dep[-1])

    return ma
print(alt_solve(a),ans1,ans2)

input()
brackets = list(map(int, input().split()))
depth = 0
rn_longest = 0
sq_longest = 0
alt_depth = 0
max_alt_depth = 0
last_alt = (alt_depth, 1 if brackets[0] == 3 else 3)
same_rep = [0]
sq_start = (-2, 0) # index, -2 if not found
rn_start = (-2, 0) # , depth - 1

for i in range(len(brackets)):
    b = brackets[i]
    if b in [1, 3]:
        depth += 1
        if b != last_alt[1]:
            alt_depth += 1
            last_alt = (alt_depth, b)
            max_alt_depth = max(alt_depth, max_alt_depth)
            same_rep += [0]
        else:
            same_rep[-1] += 1
        if sq_start[0] == -2 and b == 3:
            sq_start = (i - 1, depth - 1)
        elif rn_start[0] == -2 and b == 1:
            rn_start = (i - 1, depth - 1)
    else:
        depth -= 1
        if b == last_alt[1] + 1:
            if same_rep[-1] > 0:
                same_rep[-1] -= 1
            else:
                alt_depth -= 1
                last_alt = (alt_depth, 1 if b == 4 else 3)
                same_rep.pop(-1)
        if sq_start[1] == depth and b == 4:
            sq_longest = max(sq_longest, i - sq_start[0])
            sq_start = (-2, 0)
        elif rn_start[1] == depth and b == 2:
            rn_longest = max(rn_longest, i - rn_start[0])
            rn_start = (-2, 0)
    # print(i + 1, alt_depth, same_rep)
    if depth == 0:
        if i < len(brackets) - 1:
            last_alt = (alt_depth, 1 if brackets[i+1] == 3 else 3)
print(max_alt_depth, rn_longest, sq_longest)

def solve(s, op, cl):
    if op not in s:
        return 0
    
    st = []
    le = mle = 0

    for c in s:
        if c == op:
            st.append(c)
        if c == cl:
            st.pop()

        le += 1

        if not st:
            if le > mle:
                mle = le

            le = 0

    return mle


def alt_solve(s):
    pre = []
    dep = []
    ma = 0

    for c in s:
        if c == ')' or c == ']':
            pre.pop()
            dep.pop()
            continue

        if not pre:
            pre.append(c)
            dep.append(1)

        elif c != pre[-1]:
            pre.append(c)
            dep.append(dep[-1] + 1)

        else:
            pre.append(c)
            dep.append(dep[-1])

        if dep:
            ma = max(ma, dep[-1])

    return ma

n = int(input())
x = '()[]'
s = ''.join(x[i - 1] for i in list(map(int, input().split())))

print(alt_solve(s), solve(s, '(', ')'), solve(s, '[', ']'))


def solve(s, op, cl):
    st = []
    le = mle = 0

    for c in s:
        if c == op:
            st.append(c)
        if c == cl:
            st.pop()

        le += 1

        if not st:
            if le > mle:
                mle = le

            le = 0

    return mle


def alt_solve(s):
    pre = []
    dep = []
    ma = 0

    for c in s:
        if c == ')' or c == ']':
            pre.pop()
            dep.pop()
            continue

        if not pre:
            pre.append(c)
            dep.append(1)

        elif c != pre[-1]:
            pre.append(c)
            dep.append(dep[-1] + 1)

        else:
            pre.append(c)
            dep.append(dep[-1])

        if dep:
            ma = max(ma, dep[-1])

    return ma

n = int(input())
x = '()[]'
s = ''.join(x[i - 1] for i in list(map(int, input().split())))

print(alt_solve(s), solve(s, '(', ')'), solve(s, '[', ']'))


def solve(s, op, cl):
    st = []
    le = mle = 0

    for c in s:
        if c == op:
            st.append(c)
        if c == cl:
            st.pop()

        le += 1

        if not st:
            if le > mle:
                mle = le

            le = 0

    return mle


def alt_solve(s):
    pre = []
    dep = []
    ma = 0

    for c in s:
        if (c == '(' or c == '[') and pre == []:
            pre.append(c)
            dep.append(1)

        elif (c == '(' and pre[-1] == '[') or (c == '[' and pre[-1] == '('):
            pre.append(c)
            dep.append(dep[-1] + 1)

        elif c == '(' or c == '[':
            pre.append(c)
            dep.append(dep[-1])

        elif c == ')' or c == ']':
            pre.pop()
            dep.pop()

        if dep:
            ma = max(ma, dep[-1])

    return ma

n = int(input())
x = '()[]'
s = ''.join(x[i - 1] for i in list(map(int, input().split())))

print(alt_solve(s), solve(s, '(', ')'), solve(s, '[', ']'))


n = int(input())
br = [int(i) for i in input().split()]
n = len(br)
alt_count = 0
prev_alt = -1
max_alt = 0

flag1 = flag2 = 0
start1 = start2 = max1 = max2 = 0
help_arr = [[0, 0]]

for i in range(n):
    if br[i] == 1:
        if flag1 == 0: start1 = i
        flag1 += 1
    elif br[i] == 2:
        flag1 -= 1
        if flag1 == 0 and i - start1 > max1:
            max1 = i - start1
            #print(start1, i)
    elif br[i] == 3:
        if flag2 == 0: start2 = i
        flag2 += 1
    elif br[i] == 4:
        flag2 -= 1
        if flag2 == 0 and i - start2 > max2:
            max2 = i - start2
    x = 0
    if br[i] == 1 or br[i] == 3:
        if help_arr[-1][1] != br[i]:
            x = 1
        help_arr.append([help_arr[-1][0] + x, br[i]])
        if help_arr[-1][0] > max_alt: max_alt = help_arr[-1][0]
    else:
        help_arr.pop(-1)
if 1 not in br:
    max1 = -1
if 3 not in br:
    max2 = -1
print(max_alt, max1 + 1, max2 + 1)


# cook your dish here
n = int(input())
a = list(map(int, input().split()))
q = []
temp = 0
depth = 0
bracket = [0, 0]
brac_count = [0, 0]
brac_ind = [0, 0]

for i, v in enumerate(a):
    if v == 1 or v == 3:
        if v == 1:
            if brac_count[0] == 0:
                brac_ind[0] = i
            brac_count[0] += 1
        else:
            if brac_count[1] == 0:
                brac_ind[1] = i
            brac_count[1] += 1
                
        if not q or v != q[-1]:
            temp += 1
        q.append(v)
    else:
        depth = max(temp, depth)
        if len(q) < 2 or q[-1] != q[-2]:
            temp -= 1
        q.pop()
        if v == 2:
            brac_count[0] -= 1
            if brac_count[0] == 0:
                bracket[0] = max(bracket[0], i - brac_ind[0]+1)
        else:
            brac_count[1] -= 1
            if brac_count[1] == 0:
                bracket[1] = max(bracket[1], i - brac_ind[1]+1)
        
print(depth, bracket[0], bracket[1])

def max_len_between(s, paren_type):
    st = []
    length = 0
    max_length = 0

    op = paren_type[0]
    cp = paren_type[1]

    for c in s:
        if c == op:
            st.append(c)
        elif c == cp:
            st.pop()

        if len(st) == 0:
            if length > max_length:
                max_length = length + 1
            length = 0
        else:
            length += 1

    return max_length

def parser(arr):
    return [{1 : '(', 2 : ')', 3 : '[', 4 : ']'}[c] for c in arr]

n = int(input())
a = list(map(int, input().split()))

br = []
dep = []

ret = 0

for i in range(0, n):
    if (a[i] == 1 or a[i] == 3) and br == []:
        br.append(a[i])
        dep.append(1)
        ret = max(ret, dep[-1])

    elif a[i] == 1 and br[-1] == 3:
        br.append(a[i])
        dep.append(dep[-1] + 1)
        ret = max(ret, dep[-1])

    elif a[i] == 3 and br[-1] == 1:
        br.append(a[i])
        dep.append(dep[-1]+1)
        ret = max(ret, dep[-1])

    elif a[i] == 1 or a[i] == 3:
        br.append(a[i])
        dep.append(dep[-1])
        ret = max(ret, dep[-1])

    elif a[i] == 2 or a[i] == 4:
        br.pop()
        dep.pop()

print(ret, max_len_between(parser(a), '()'), max_len_between(parser(a), '[]'))

n=int(input())

a=[int(x) for x in input().split()]
k,d=0,0
st=[]

st.append(a[0])
k,d=1,1
for i in range(1,n):
    if a[i]==1 or a[i]==3:
        st.append(a[i])

        if st[len(st)-1]!=st[len(st)-2]:
            k+=1
            if k>d:
                d+=1
        #print(st,k,d)
    else:
        try:
            if st[len(st)-1]!=st[len(st)-2]:
                k-=1
            st.pop()
        except:
            st.pop()
            k-=1
        #print(st,k,d)

c1,max1=0,0
s1=[]
for i in range(n):
    try:
        if len(s1)==0 and a[i]==1:
            s1.append(a[i])
            c1+=1
        elif len(s1)!=0 and (a[i]==1 or a[i]==3):
            s1.append(a[i])
            c1+=1

        elif a[i]==2 or a[i]==4:
            s1.pop()
            c1+=1
        if max1 < c1:
            max1 = c1
        if len(s1)==0:
            c1=0
    except:
        pass



c2,max2=0,0
s2=[]
for i in range(n):
    try:
        if len(s2)==0 and a[i]==3:
            s2.append(a[i])
            c2+=1
        elif len(s2)!=0 and (a[i]==1 or a[i]==3):
            s2.append(a[i])
            c2+=1

        elif a[i]==2 or a[i]==4:
            s2.pop()
            c2+=1
        if max2 < c2:
            max2 = c2
        if len(s2)==0:
            c2=0
    except:
        pass

print(d,max1,max2)